分卡牌
题目描述
小A和小B正在玩一个卡牌游戏，该游戏中共有N张卡牌，每张卡牌都有一个分数S，小A和小B希望将这N张卡牌分成分数相等的两份（每份中的卡牌数量不一定相等）。请帮助小A和小B计算，是否可以将卡牌分成分数相等的两份，如果可以输出YES，否则输出NO。
输入格式
输入文件：card.in
第1行：一个正数T，代表测试数据的组数
每组数据第1行：一个正数N，代表卡牌的数量
每组数据第2行：N个空格分隔的正整数，第i个数代表卡牌i上的分数si 。
输出格式
输出文件：card.out
每组测试数据输出一行：如果可以分成分数相等的两份输出YES,否则输出NO
输入输出样列
输入样例1：
2
3
1 2 3
2
1 3
输出样例1：
YES
NO
说明
【样例说明】
样例1中共有2组测试数据：
第一组数据：将前两张卡牌分在一起，总分数为3，将第3张卡牌分成另一组，总分数也是3。可以将卡牌分成分数相等的两份。
第二组数据：无论如何都无法分成分数相等的两份。
【数据范围】：
对于100%的数据，1≤T≤50，2≤N≤100，1≤si≤100
DM:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>
using namespace std;
int s[110];
bool d[100*100/2+10];
int main()
{
int t;
cin>>t;
while(t--){
int sum=0,n;
memset(d,0,sizeof(d));
cin>>n;
for(int i=1;i<=n;i++){cin>>s[i]; sum+=s[i];}
if(sum%2){
cout<<"NO"<<endl;
continue;
}
sum/=2;
d[0]=1;
for(int i=1;i<=n;i++){
for(int j=sum;j>=s[i];j--){
d[j]=d[j] || d[j-s[i]]; //这里的写法
}
}
if(d[sum])cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
