可以免费发广告的网站,做办公室的网站,医学网站建设风格,网站备案幕布大小题目链接 8VC Venture Cup 2016 - Elimination Round 题意 把$n$个物品分成若干组#xff0c;每个组的代价为组内价值的极差#xff0c;求所有组的代价之和不超过$k$的方案数。 考虑DP#xff0c;$f[i][j][k]$表示考虑到第$i$个物品的时候#xff0c;还有$j$组尚未分配完…题目链接 8VC Venture Cup 2016 - Elimination Round 题意 把$n$个物品分成若干组每个组的代价为组内价值的极差求所有组的代价之和不超过$k$的方案数。 考虑DP$f[i][j][k]$表示考虑到第$i$个物品的时候还有$j$组尚未分配完毕当前状态总代价为$k$的方案数。 先把$a[]$升序排序那么极差就可以转化为后面的元素减前面的元素不停叠加的效果。 当考虑第$i$个物品的时候有$4$种转移方法 当前物品新开一组并且继续等待分配 当前物品新开一组并且这个物品单独当做一种 当前物品插入到之前的$j$组中的一组中去并让这个组继续等待分配那么有$j$种插入的方案 当前物品插入到之前的$j$组中的一组中去并作为这个组的最大值停止分配同样有$j$种插入的方案。 时间复杂度$O(n^{2}k)$ #include bits/stdc.husing namespace std;#define rep(i, a, b) for (int i(a); i (b); i)
#define dec(i, a, b) for (int i(a); i (b); --i)
#define MP make_pair
#define fi first
#define se secondtypedef long long LL;const int N 202;
const int M 1010;
const LL mod 1e9 7;int n, m;
int a[N];
int x;
LL f[2][N][M];
LL ans;void up(LL x, LL y){ x x y; x % mod;}int main(){scanf(%d%d, n, m);rep(i, 1, n) scanf(%d, a i);sort(a 1, a n 1);a[0] a[1];f[0][0][0] 1;x 1;rep(i, 0, n - 1){x ^ 1;memset(f[x ^ 1], 0, sizeof f[x ^ 1]);rep(j, 0, i){rep(k, 0, m) if (f[x][j][k] k j * (a[i 1] - a[i]) m){int cnt k j * (a[i 1] - a[i]);up(f[x ^ 1][j 1][cnt], f[x][j][k]);up(f[x ^ 1][j][cnt], f[x][j][k]);if (j){up(f[x ^ 1][j][cnt], f[x][j][k] * j % mod);up(f[x ^ 1][j - 1][cnt], f[x][j][k] * j % mod);}}}}ans 0;rep(i, 0, m) up(ans, f[x ^ 1][0][i]); printf(%lld\n, ans);return 0;
}转载于:https://www.cnblogs.com/cxhscst2/p/8578369.html
