传送门
很新颖的一个布尔dp，我们用dp[i][j]表示选i个人能否构成j的血量
注意，是“能否”，也就是说dp存的是一个逻辑变量。
首先考虑一些细节，对于偶数的n，那么两个部队人数肯定是i/2，对于奇数，为i/2(向下取整)和i/2+1
考虑如何进行状态转移，dp[i][j]=dp[i][j] | dp[i-1][j-val[k]，这个方程挺像背包，所以应该没什么难度。
多说一句 这份代码会被3 1 1 3 hack掉，网上几乎所有的dp题解都会被hack掉，我一直在思考是哪个细节出了问题，最终无果，望大佬能够指点一波。
//bool-dp #include<bits/stdc++.h> #define N 205 using namespace std; int n,val[N],dp[N][N],sum; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>val[i]; sum+=val[i]; } dp[0][0]=true; for(int i=1;i<=n;i++) { for(int j=n/2;j>=1;j--) { for(int k=sum;k>=val[i];k--) { dp[j][k]=dp[j][k]|dp[j-1][k-val[i]]; // cout<<"i:"<<i<<" "<<"j:"<<j<<" "<<"k:"<<k<<" "<<z"data:dp[j][k]="<<dp[j][k]<<endl; } } } for(int i=sum/2;i>=0;i--) { if(dp[n/2][i]==true){ cout<<i<<" "<<sum-i; return 0; } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9495887.html
相关资源：猫狗大战数据集