博客食用更佳~
https://www.cnblogs.com/czyty114/p/14766344.html
题意: https://www.luogu.com.cn/problem/P7519
Solution
暴力
暴力枚举每种排列,显然排名是按照bi不降的顺序也单调升高
所以只需让当前队伍排第一的前提下让bi的尽可能的小即可。
如果发现∑bi<=m,一定是存在一种方案的(让最后一个队伍过题数更多就行了)
状压dp
考虑设计状态。
首先目前已选队伍的集合S一定得有,然后是目前总过题数k
显然,你还关心上个队伍的编号和bj
因为按照暴力的贪心思路,我们要让当前的bi尽可能的小。假设上个队伍为j
即:ai+bi≥aj+bj,bi≥aj+bj−ai
但这样的时间复杂度是
O(2n×n2×m2)的
考虑简化状态。
再次考虑bi的不降性,得到:bi=max(bj,bj+aj−ai),即:bi=bj+max(0,aj−ai)
最终我们一定选了n支队伍,那么∑bi一定是
∑max(0,aj−ai)×(n−pi+1)
pi代表i队伍是第几个选的。
换句话来说,第i支队伍对答案的贡献可以简化为max(0,aj−ai)×(n−pi+1)
所以我们没有必要知道bi具体的值是多少,而是只需要知道他对最终答案的贡献是多少就可以了。
这实质是一个提前算贡献的思想(不关心过程,只关心它对最终结果造成的影响)
所以就可以把上个队伍bj给删去。
而现在的k就不是目前选题总个数了(而是最终对答案影响的贡献)
最终复杂度:O(2n×n2×m)
Code
#include <bits/stdc++.h>
const int N = 13, M = 505;
#define ll long long
int n, m, a[N];
ll f[1 << N][N + 1][M];
int main() {
scanf("%d%d", &n, &m);
int t = n;
for (int i = 0; i < n; i ++) {
scanf("%d", &a[i]);
if (a[i] > a[t]) t = i;
}
for (int i = 0; i < n; i ++) {
int add = n * (a[t] - a[i] + (i > t));
if (add <= m) f[1 << i][i][add] = 1;
}
for (int i = 1; i < (1 << n); i ++) {
int cnt = 0;
for (int j = 0; j < n; j ++) if (i >> j & 1) cnt ++;
for (int j = 0; j < n; j ++) if (i >> j & 1)
for (int k = 0; k <= m; k ++)
for (int l = 0; l < n; l ++) if ((i | (1 << l)) != i) {
int add = (n - cnt) * std::max(0, a[j] - a[l] + (l > j));
if (k + add <= m) f[i | (1 << l)][l][k + add] += f[i][j][k];
}
}
ll ans = 0;
for (int i = 0; i < n; i ++)
for (int j = 0; j <= m; j ++)
ans += f[(1 << n) - 1][i][j];
printf("%lld", ans);
return 0;
}