HDU 5000 Clone

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

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

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

代码：

#include 
  
   
#include 
   
     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; }