P2392 kkksc03考前临时抱佛脚 题解

1.题外话

kkksc03成功把我吸引过来~

最近正好在复习基础,看到pj-的难度就想水一题。

2.解题意

4个科目,互不影响,说白了就是4组数据。给你四组数据,对于每一组数据,我们将其分成两组,使得max(sum1,sum2)最小,sum1和sum2分别指的是两组数据的和。

3.找思路

很明显,要使和最大的一组和尽量小,我们只需使和更小的那一组和尽量大,也就是和最接近于sum/2(sum是所有数据的和)即可。问题接着转化成了:上限为sum/2的01背包问题。

每一个物品的体积可以看做数的大小,进而进行01背包dp即可。

4.奇怪的代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
using namespace std;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int sum,s[5],sum0,a[21],dp[1300];
int main()
{
    int t=4;
    for(int i=1;i<=4;i++)
    s[i]=read();
    for(int t=1;t<=4;t++)//四科
    {
        int sumt=0;sum0=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=s[t];i++)
        {
            a[i]=read();sumt+=a[i];
        }
        for(int i=1;i<=s[t];i++)
        {
            for(int j=sumt>>1;j>=a[i];j--)
                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
        sum+=sumt-dp[sumt>>1];
    }
    printf("%d",sum);
    return 0;
}

 

上一篇:P2392 kkksc03考前临时抱佛脚题解


下一篇:洛谷 P2392 kkksc03考前临时抱佛脚, dp / 深搜