P2392 kkksc03考前临时抱佛脚
Captain_Paul
2017-10-15 14:10:22
这道题可以运用dp方法求解，建议与P1489猫狗大战配合食用，效果更佳。
这道题的目的就是将每一科目的所有数分成两部分，使得两部分的差最小。
首先，对于每一科目，用布尔类型数组f[i][j]表示i个数中取得总和j是否可行，可行则为true，否则为false。
显然，初始化使得f[0][0]=1.
本题的输入数据可以用二维数组来存储，那么状态转移方程可以表示为:f[j][k]=f[j][k]||f[j-1][k-a[t][i]]
然后我们可以从sum[t]>>1开始枚举，若f[j][i](1<=j<=n)为true，则答案为max(i,sum[t]-i)，退出函数即可。
将以上过程重复四次，累加所得答案，输出andAC！
代码如下：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[25][1205];
int s1,s2,s3,s4,a[5][25];
int ans[5],sum[5],answer;
void dp(int t,int n)
{
int nn;
if (n==1)
{
ans[t]=sum[t];
return;
}
memset(f,0,sizeof(f));
f[0][0]=1;
//if (n&1) nn=n/2+1;
//else nn=n/2;
for (int i=1;i<=n;i++)
for (int j=n;j>=1;j--)
for (int k=sum[t]>>1;k>=a[t][i];k--)
f[j][k]=f[j][k]||f[j-1][k-a[t][i]];
for (int i=sum[t]>>1;i>=0;i--)
for (int j=1;j<=n;j++)
if (f[j][i])
{
ans[t]=max(i,sum[t]-i);
return;
}
}
int main()
{
int i,j;
scanf("%d%d%d%d",&s1,&s2,&s3,&s4);
for (i=1;i<=s1;i++) scanf("%d",&a[1][i]),sum[1]+=a[1][i];
for (i=1;i<=s2;i++) scanf("%d",&a[2][i]),sum[2]+=a[2][i];
for (i=1;i<=s3;i++) scanf("%d",&a[3][i]),sum[3]+=a[3][i];
for (i=1;i<=s4;i++) scanf("%d",&a[4][i]),sum[4]+=a[4][i];
dp(1,s1); dp(2,s2); dp(3,s3); dp(4,s4);
//cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<" "<<ans[4]<<endl;
for (i=1;i<=4;i++) answer+=ans[i];
printf("%d\n",answer);
return 0;
}
```