hdu 5000 共存问题->背包

时间：2021-06-20 08:25:37

http://acm.hdu.edu.cn/showproblem.php?pid=5000

每只羊有n个属性

下面n个数字表示每个属性的值范围为[ 0, T[i] ]

对于羊圈里的a羊和b羊，若a羊的每个属性都>=b羊，则a羊会杀死b羊。

问羊圈里最多存活多少只羊。

sum相同的羊不会互相杀死。

sum不同的羊不会重合。（我们设a羊sum = x，b羊sum = y，若a，b羊能共存，但不会把ab同时放到羊圈里。

因为一定存在一只羊c ，sum = x，且c和b不能共存，既然不能共存，则我们放入c羊是不会影响答案的。）

sum其实是对称的，和组合数一样。所以dp[n][求和(T[i]) / 2] 是最大的。

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

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include<set>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

const int modo = 1e9 + 7;

int s[2004];

int dp[2004][1004];

int main() {

    int _,n;

    RD(_);

    while(_--){

        RD(n);

        int sum = 0;

        for(int i = 0;i < n;++i){

            RD(s[i]);

            sum += s[i];

        }

        sum /= 2;

        clr0(dp);

        for(int i = 0;i <= s[0];++i)

            dp[0][i] = 1;

        for(int i = 1;i < n;++i){

            for(int j = 0;j <= sum;++j){

                for(int k = 0;k + j <= sum && k <= s[i];++k)

                    dp[i][k+j] = (dp[i-1][j] + dp[i][k+j])%modo;

            }

        }

        cout<<dp[n-1][sum]<<endl;

    }

    return 0;

}

相关文章