hdu5000 Clone dp+大数

After eating food from Chernobyl, DRD got a super power: he could clone himself right now! He used this power for several times. He found out that this power was not as perfect as he wanted. For example, some of the cloned objects were tall, while some were short; some of them were fat, and some were thin.

More evidence showed that for two clones A and B, if A was no worse than B in all fields, then B could not survive. More specifically, DRD used a vector v to represent each of his clones. The vector v has n dimensions, representing a clone having N abilities. For the i-th dimension, v[i] is an integer between 0 and T[i], where 0 is the worst and T[i] is the best. For two clones A and B, whose corresponding vectors were p and q, if for 1 <= i <= N, p[i] >= q[i], then B could not survive.

Now, as DRD's friend, ATM wants to know how many clones can survive at most.

题意：有许多克隆人，每个人都有 N 项属性，每个属性都有上限，每个克隆人的属性是 1 到该属性上限的一个整数。现在如果有克隆人所有属性都小于等于另外某个克隆人，那么他就无法生存，问给定每个属性上限，最多有多少克隆人可以生存。

N范围2000，所有属性上限的总和范围也是2000。

其实最优的情况是所有克隆人属性总和都相等，那么一定有人在这个属性比较优，而其他的在另一个属性比较优，前提是没有两个人所有属性均相等。

那么问题其实就变成了如果我知道属性总和，有多少种不同的构成这个总和的方法？然后对于所有总和都求一遍，取一个最大值就可以了。

那么就变成了非常经典的DP思路，拆分数字。

DP[ i ][ j ] 表示选取完第 i 个数，总和是 j 的情况总数；

第 i 个数的取值范围是 1 ～ T[ i ]，T[ i ] 是第 i 个属性的上限；

枚举这个数的取值是 k ，DP[ i ][ j ] = ∑ ( k:1~T[i] ) ( DP[ i-1 ][ j-k ] )；

然后因为 j 是前一层中 j 较小的一部分的和，所以可以从后往前更新，压缩掉 i 这一维。

用大数写。

 import java.util.*;

 import java.math.BigInteger;

 public class Main {

     static int t[]=new int[];

     static BigInteger dp[]=new BigInteger[];

     static BigInteger mmod = BigInteger.valueOf();

     public static void main(String[] args){

         Scanner input = new Scanner(System.in);

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

             t[i]=;

             dp[i]=BigInteger.ZERO;

         }

        int T=input.nextInt();

        while(T--!=){

            int n=input.nextInt();

            int i=,sum=;

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

                t[i]=input.nextInt();

                sum+=t[i];

            }

            sum=sum*/;

            for(i=;i<=;++i)dp[i]=BigInteger.ZERO;

            BigInteger mx=BigInteger.ZERO;

            dp[]=BigInteger.ONE;

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

                for(int j=sum;j>;--j){

                    for(int k=;k<=t[i]&&j>=k;++k){

                        dp[j]=dp[j].add(dp[j-k]);

                    }

                }

            }

            for(i=;i<=sum;++i){

                if(mx.compareTo(dp[i])<)mx=dp[i];

            }

            mx=mx.mod(mmod);

            System.out.println(mx);

        }

        input.close();

     }

 }

巴特西

hdu5000 Clone dp+大数

最新文章

热门文章