寂寞香菇

文章
4
资源
0
加入时间
3年2月3天

[agc009c]Division into Two前言题目大意DP

前言DP题,还可以,不是很难。题目大意把一堆互不相同的数分成两个集合X和Y,其中一个集合X任意两数之差不小于A,另一集合Y任意两数之差不小于B。 问方案数,集合可以为空。DP把这些数排序。 接着添加第0个数无穷小以及第n+1个数无穷大。 我们假设A>=B。 设f[i]表示分配好了前i个数,第i个数去X集合的方案。 转移显然要找到上一个位置j。 第一种情况j=i-1,只要a[i]-a[i-