dfs+剪枝+记忆化搜索（二维01背包）

牛客小白月赛112 E

dfs写的最牢的一局，赛时dp和dfs混着用，一个多小时写了删删了写，结果样例没过。样例过了，剪枝和记忆化不太会，被卡爆

dfs写法

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=105;
int n,m;
int a[N];
vector<int> va,vb;
bool mark=false;
int x;
bool vis[N][N][N];
void dfs(int cnt,int suma,int sumb,int ta,int tb){
    if(mark) return;
    if(suma*sumb>x) return;
    if(suma>ta||sumb>tb) return;
    if(ta==suma&&tb==sumb){
        mark=true;
        return;
    }
    if(cnt>n) return;
    if(vis[cnt][suma][sumb]) return;
    vis[cnt][suma][sumb]=true;
    if(suma+a[cnt]<=ta){
        va.push_back(a[cnt]);
        dfs(cnt+1,suma+a[cnt],sumb,ta,tb);
        if(mark) return;
        va.pop_back();
    }
    if(sumb+a[cnt]<=tb){
        vb.push_back(a[cnt]);
        dfs(cnt+1,suma,sumb+a[cnt],ta,tb);
        if(mark) return;
        vb.pop_back();
    }
    dfs(cnt+1,suma,sumb,ta,tb);
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(m--){
        cin>>x;
        mark=false;
        for(int i=1;i*i<=x;i++){
            if(x%i)continue;
            int j=x/i;
            va.clear(),vb.clear();
            memset(vis, false, sizeof(vis));
            dfs(1,0,0,i,j);
            if(mark){
                break;
            }
        }
        if(mark){
            cout<<"Yes"<<endl;
            cout<<va.size()<<" "<<vb.size()<<endl;
            for(auto num:va) cout<<num<<" ";
            cout<<endl;
            for(auto num:vb){
                cout<<num<<" ";
            }
            cout<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

dp写法

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=105;
int a[N];
int n,m;
bool dp[N*N][N*N];
int pre[N*N][N*N];
void find(int x,int y,vector<int> &va,vector<int> &vb){
    if(x==0&&y==0) return;
    // cout<<pre[x][y]<<endl;
    // cout<<x<<" "<<y<<endl;
    if(pre[x][y]>0) {
        va.push_back(pre[x][y]);
        find(x-pre[x][y],y,va,vb);
    }
    else {
        vb.push_back(-pre[x][y]);
        find(x,y+pre[x][y],va,vb);
    }
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    dp[0][0]=true;
    for(int i=1;i<=n;i++){
        for(int j=100;j>=0;j--){
            for(int k=100;k>=0;k--){
                if(dp[j][k]) continue;
                if(j>=a[i]&&dp[j-a[i]][k]){
                    dp[j][k]=true;
                    pre[j][k]=a[i];
                }
                if(k>=a[i]&&dp[j][k-a[i]]){
                    dp[j][k]=true;
                    pre[j][k]=a[i]*-1;
                }
            }
        }
    }
    // for(int i=0;i<=sum;i++){
    //     for(int j=0;j<=sum;j++){
    //         cout<<dp[i][j]<<" "<<pre[i][j]<<endl;
    //     }
    //     cout<<endl;
    // }
    while(m--){
        int x;
        cin>>x;
        bool mark=false;
        for(int i=1;i*i<=x;i++){
            if(x%i) continue;
            int j=x/i;
            if(dp[i][j]){
                // cout<<dp[i][j]<<endl;
                // cout<<i<<" "<<j<<endl;
                cout<<"Yes"<<endl;
                mark=true;
                vector<int> va,vb;
                find(i,j,va,vb);
                cout<<va.size()<<" "<<vb.size()<<endl;
                for(auto& num:va){
                    cout<<num<<" ";
                }
                cout<<endl;
                for(auto& num:vb){
                    cout<<num<<" ";
                }
                cout<<endl;
            }
            if(mark) break;
        }
        if(!mark){
            cout<<"No"<<endl;
        }
    }
    return 0;
}