这题是网络赛的一个题.基本上属于猜想性的题目.很多东西不能深究,得猜,而猜也是有技巧的,可以暴力打表.

题意:clones有一些属性,每一个属性都是0-w[i]的任意一个值.每个clone都得有每个属性各一个属性值.如果制造出一堆这样的clones,他们之间不能存在一个clone的各方面属性都不小于另一个clone,求满足条件的最多clones数量.

思路:

dilworth定理和这个有点关系,但是好像没办法解这个题.也就是求一个反链使得里面包含的所有个体都不可比,即求最长反链,那么应该等于最少链覆盖数.然后就没有然后了...

猜想一,满足最多数量clones数的时候必然这些所有clone的属性之和都相等,等于一个定值.然而这题结果太大了,需要取模,所以如果dp求出所有属性之和,然后比较是不对的,取模..所以仅仅是这个猜想还是不够的.

猜想二,这个定值等于所有属性最大值之和除以2.这个能想到的大部分可能是因为题目描述中弱弱的说了一句 "It guarantees that the sum of T[i] in each test case is no more than 2000 and 1 <= T[i]. " 所有属性和不超过2000,如果和这个东西没关系说它干嘛.所以..

有了这两个猜想,写一个dp类似于背包就可以了.

后来到网上看了看,有人说了一个挺有道理的支持猜想二的说法.

如果有一个骰子,然你抛两次,两次得到的数字之和概率最大的是多少.就是说两次数字的和是哪一个数的时候概率最大.想想好像是7,为什么呢,因为无论第一次是哪一个数,第二次总有一个数可能和它的和是7,怎么求出来的呢.7=(6+6)/2+1,那么上题按照这个思路应该是sum/2+1才对,这不错了么?注意骰子上没有0!!而上题是从0开始的.具体原因我再想想.

AC代码:

1 #include 
         
           2 #include 
          
            3 #include 
           
             4 #include 
            
              5 #include 
             
               6 #include 
              
                7 using namespace std; 8 #define maxn 2005 9 #define MOD 100000000710 int f[maxn][maxn],t[maxn];11 int main()12 {13 int T,n,i,j,k,m;14 scanf("%d",&T);15 while(T--)16 {17 m=0;18 scanf("%d",&n);19 for(i=1;i<=n;i++)20 {21 scanf("%d",&t[i]);22 m+=t[i];23 }24 m/=2;25 memset(f,0,sizeof(f));26 for(i=0;i<=t[1];i++)27 f[1][i]=1;28 for(i=2;i<=n;i++)29 for(j=0;j<=m;j++)30 {31 for(k=0;k<=t[i];k++)32 if(j>=k)33 f[i][j]=(f[i][j]+f[i-1][j-k])%MOD;34 }35 cout<
               
                <