01二维背包+bitset优化——hdu5890

发布时间：2020-12-14 04:41:36 所属栏目：大数据来源：网络整理

导读：口胡一种别的解法：三重退背包，g1[j]k]表示不选x的选了j件物品，体积为k的方案数，g[0][0] = 1,g1[j][k]=dp[j][k]-g1[j-1][k-a[x]] 然后按这样再退三层,最后看g3[10][87]的方案数是否非0即可，这样复杂度是O(50*50*50*10*87) 如果直接枚举删掉的数，然后用

口胡一种别的解法：

三重退背包，g1[j]k]表示不选x的选了j件物品，体积为k的方案数，g[0][0] = 1,g1[j][k]=dp[j][k]-g1[j-1][k-a[x]]

然后按这样再退三层,最后看g3[10][87]的方案数是否非0即可，这样复杂度是O(50*50*50*10*87)

如果直接枚举删掉的数，然后用可行性二维01背包做

复杂度是O(50*50*50)*O(n*10*87)?再加上bitset优化第二维?复杂度/32,由于n比较小，所以也差不多

/*
在n个数里找到三个数删去，问取10个数能否凑成87 
dp[i][j]表示选i个数凑出 
*/
#include<bits/stdc++.h>
using namespace std;
int n,a[100],ans[55][55][55];

bitset<100>dp[12];
void calc(int x,int y,int z){
    for(int i=0;i<=11;i++)dp[i].reset();
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        if(i!=x && i!=y && i!=z)
            for(int j=10;j>=1;j--)
                dp[j]|=(dp[j-1]<<a[i]);
    if(dp[10][87])
        ans[x][y][z]=1;
    else ans[x][y][z]=0;
}

int main(){
    int t;cin>>t;
    while(t--){
        memset(ans,0,sizeof ans);
        
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)
                for(int k=j;k<=n;k++)
                    calc(i,j,k); 
        
        int q;cin>>q;
        while(q--){
            int s[3];
            scanf("%d%d%d",&s[0],&s[1],&s[2]);
            sort(s,s+3);
            if(ans[s[0]][s[1]][s[2]])
                puts("Yes");
            else puts("No");
        }
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!