P2392 kkksc03考前临时抱佛脚

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为true,则答案为max(i,sum[t]-i),退出函数即可。

将以上过程重复四次,累加所得答案,输出andAC!

代码如下:

#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;
}