求助,用的01背包,但是全WA(哭)
查看原帖
求助,用的01背包,但是全WA(哭)
1049051
JiuZhE66666楼主2023/9/4 10:26
#include<bits/stdc++.h>
using namespace std;
int s[6]={0},a[80]={0},total=0,bag[80][80]={0},sum=0;
void bb(int len)
{
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=len;j++)
        {
            bag[i][j]=(abs(total-2*bag[i][j-1])<abs(total-2*(bag[i-1][j-1]+a[j])))?bag[i][j-1]:(bag[i-1][j-1]+a[j]);
            bag[i][j]=(abs(total-2*bag[i][j])<abs(total-2*bag[i-1][j]))?bag[i][j]:bag[i-1][j];
            
        }
     
    }
    
    sum+=max(bag[len][len],total-bag[len][len]);
}
int main()
{
    cin>>s[0]>>s[1]>>s[2]>>s[3];


    for(int i=0;i<4;i++)
    {


        for(int j=1;j<=s[i];j++)
        {
            cin>>a[j];
            total+=a[j];
        }


        bb(s[i]);

        memset(bag,0,sizeof(bag));
        memset(a,0,sizeof(a));
        total=0;
    }
    cout<<sum;
    return 0;
}
2023/9/4 10:26
加载中...