HDU 5000 Clone（鞍山网络赛D题）

本文主要是介绍HDU 5000 Clone（鞍山网络赛D题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 5000 Clone

这场就出了3题。。就坑在这题上了，还好保住了名额

思路：要推出最大值的时候，每个人的属性和必然相同，并且这个和必然是所有和 / 2，这样的话，问题转化为给n个数字，要组合成sum / 2有多少种方法，就用dp背包推一遍就可以得解了。

现场的时候就没推出sum / 2就是答案

代码：

#include <cstdio>
#include <cstring>const int MOD = 1000000007;const int N = 2005;int t, n, dp[N], T[N];int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);int sum = 0;for (int i = 1; i <= n; i++) {scanf("%d", &T[i]);sum += T[i];}sum /= 2;memset(dp, 0, sizeof(dp));dp[0] = 1;for (int i = 1; i <= n; i++) {for (int k = sum; k >= 0; k--) {for (int j = 1; j <= T[i]; j++) {if (k - j < 0) break;dp[k] = (dp[k] + dp[k - j]) % MOD;}}}printf("%d\n", dp[sum]);}return 0;
}

这篇关于HDU 5000 Clone（鞍山网络赛D题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---