UVA10482 The Candyman Can 题解
XingChen_MoNian
·
·
题解
前记
题目传送门。
这道题由于是英文题，翻译请看讨论贴。
再次声明：个人没有UVA账号，我没有提交，但样例过了，我的思路好像也和另一位大佬相似。
正文
首先观察此题的 n :
n \le 12
看给我激动的，暴力打起来。
这里可以考虑利用二维 dp ，设第一个孩子的糖果重量为 i ，第二个孩子的糖果重量为 j ，由于总量相同，所以第三个孩子的糖果重量为 (sum-i-j) ，则 dp[i][j] 就是表示这样的情况是否成立。
找一下状态转移方程：
如果 dp[i][j] 成立，那么 dp[i+a[i]][j] 和 dp[i][j+a[i]] 也一定成立。
最后考虑一下初始化：
来到最后的暴力搜答案，只需找到得到最大总重量糖果的孩子和得到最小总重量糖果的孩子在糖果重量上的最小差异是多少即可，也就是 $i$ , $j$ , $sum−i−j$ 的最大值到 $i$ , $j$ , $sum−i−j$ 的最小值中的最小值就可以（感觉好绕口啊）。
输出别忘了按格式输出！！！
### 代码：
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
//头文件可以用万能头
using namespace std;
typedef long long ll;
inline ll read(){
ll f=1,sum=0;char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
return sum*f;
}//经典快读模板
const int N=130+5;//n的取值
int num[N],dp[N][N];
void solve(int q,int m){
int minn=1e9,sum=0;//minn是答案，因为要取最小值，所以用了int的极限值，sum是计算总重
int n=read();
for(int i=1;i<=n;i++){
num[i]=read();
sum+=num[i];
}
memset(dp,0,sizeof(dp));//清空dp数组
dp[0][0]=1;//dp数组初始化
for(int i=1;i<=n;i++){
for(int j=sum;j>=0;j--){
for(int k=sum-j;k>=0;k--){
if(dp[j][k]){
dp[j+num[i]][k]=1;
dp[j][k+num[i]]=1;//状态转移方程
}
}
}
}//dp模板
for(int j=sum;j>=0;j--){
for(int k=sum-j;k>=0;k--){
if(dp[j][k]) minn=min(minn,max(max(j,k),sum-j-k)-min(min(j,k),sum-j-k));
}
}//暴力寻找答案
cout<<"Case "<<m-q<<": "<<minn<<endl;
//这里因为我用的是t--循环，所以要先用m记录原来t，用m减去现在的t（函数定义时换了个字母q）为编号
}
int main(){
int t=read();//多测
int m=t;//见solve函数最后一行
while(t--){
solve(t,m);
}//个人习惯
return 0;//完美地结束
}
```
### 后记
求关注awa，也求管理员通过awa。