一个人可以克隆出自己克隆体，一个克隆体有n个方面，如果一个克隆体全方面逊色于另外一个克隆体，那么它就无法存活下去，问怎样可以同时最多存活的克隆体数目。思路：得到最大值的时候，每个克隆体的属性之和必然是相同的，并且这个和是所有方面最高属性和的二分之一。问题就变成n个数组成sum/2的方案数。

#include <iostream>#include <cstdio>#include <cmath>#include <queue>#include <algorithm>#include <cstring>#include <queue>#include <iomanip>using namespace std;const int mod=1e9+7;const int maxn=2222;int n;int a[maxn];int dp[maxn];int main(){<span style="white-space:pre">	</span>int t;<span style="white-space:pre">	</span>int sum=0;<span style="white-space:pre">	</span>scanf("%d",&t);<span style="white-space:pre">	</span>while(t--)<span style="white-space:pre">	</span>{<span style="white-space:pre">		</span>sum=0;<span style="white-space:pre">		</span>scanf("%d",&n);<span style="white-space:pre">		</span>for(int i=1;i<=n;i++)<span style="white-space:pre">		</span>{<span style="white-space:pre">			</span>scanf("%d",&a[i]);<span style="white-space:pre">			</span>sum+=a[i];<span style="white-space:pre">		</span>}<span style="white-space:pre">		</span>sum/=2;<span style="white-space:pre">		</span>memset(dp,0,sizeof(dp));<span style="white-space:pre">		</span>dp[0]=1;<span style="white-space:pre">		</span>for(int i=1;i<=n;i++)//背包求n个数字组成sum的方案数 <span style="white-space:pre">		</span>{<span style="white-space:pre">			</span>for(int k=sum;k>=0;k--)<span style="white-space:pre">			</span>{<span style="white-space:pre">				</span>for(int j=1;j<=a[i];j++)<span style="white-space:pre">				</span>{<span style="white-space:pre">					</span>if(k-j<0)<span style="white-space:pre">					</span>{<span style="white-space:pre">						</span>break;<span style="white-space:pre">					</span>}<span style="white-space:pre">					</span>dp[k]=(dp[k-j]+dp[k])%mod;<span style="white-space:pre">				</span>}<span style="white-space:pre">			</span>}<span style="white-space:pre">		</span>}<span style="white-space:pre">		</span>printf("%d\n",dp[sum]);<span style="white-space:pre">	</span>}<span style="white-space:pre">	</span>return 0;}

HDU-5000 Clone 鞍山网络赛D题 DP+猜想