Lightoj 1147【DP】

题意：

把n个人分成两部分，要你怎么分使得两部分尽可能相等；

思路：

如果我们把一部分人的重量达到离sum/2最近，那就一定行啊

其实就是一条棒，两种不同的棒去拼接成一条棒，然后最好就是离mid最近，一定会得到这个值啊。

然后搞出这个值，mid-x就是他们的最小差值。不就是一个0/1背包取或不取。

然后wa了，人数相差不超过1个///

后来肯定要维护人数啊，纯粹的+，dp[j]=dp[j-a[i]]+1;这样不行啊，可能这个 j 是由多种组合过来的，

我们还是维护一半人数，最多50，所以我们可以状压，然后表示状态，比如dp[100]=6(110) 就意味着是可以4个人组合，或者2个人组合；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

LL dp[100100];

int a[110];

int n;

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        int sum,w,x;

        memset(dp,0,sizeof(dp));

        sum=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&a[i]);

            sum+=a[i];

        }

        w=sum/2;

        dp[0]=1;

        for(int i=1;i<=n;i++)

            for(int j=w;j>=a[i];j--)

                dp[j]|=(dp[j-a[i]]*2LL);

        for(int i=w;i>=0;i--)

        {

            if(dp[i]&(1LL<<((n+1)/2))||dp[i]&(1LL<<(n/2)))

            {

                x=i;

                break;

            }

        }

        printf("Case %d: %d %d\n",cas++,x,sum-x);

    }

    return 0;

}

巴特西

Lightoj 1147【DP】

最新文章

热门文章