C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<db,int> pii;
typedef vector<ll> vt;
const int N=2e5+60;
const int mod=1e8;                                              
ll f[2][1<<12][1<<12];
vt state,head[1<<12];
int g[110],cnt[1<<12];
int n,m,k;
bool check(int x){
    return !(x&x>>2||x&x>>1);
}
int calc(int x){
    int ans=0;
    while(x){
        ans+=x&1;
        x>>=1;
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);  
    cout.tie(0);
    cin>>n>>m;
    rep(i,1,n){
        rep(j,0,m-1){
            char ch;
            cin>>ch;
            g[i]+=(ch=='H')<<j;
        }
    }
    rep(i,0,(1<<m)-1){
        if(check(i)){
            state.pb(i);
            cnt[i]=calc(i);
        }
    }
    rep(i,0,sz(state)-1){
        rep(j,0,sz(state)-1){
            if((state[i]&state[j])==0){
                head[state[i]].pb(state[j]);
            }
        }
    }

    rep(i,1,n+2){
        for(int j:state){
            if(g[i]&j)continue;
            for(int k:head[j]){
                for(int l:head[k]){
                    if(j&l)continue;
                    f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][k][l]+cnt[j]);

                }
            }
        }
    }
    cout<<f[n+2&1][0][0];


    return 0;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
using std::cout;
using std::cin;
using std::endl;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define all(c) (c).begin(),(c).end()
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))
#define srt(c) sort(all(c))
#define rev(c) reverse(all(c))
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<db,int> pii;
typedef vector<ll> vt;
const int N=2e6+60;
const int mod=1e9+7;                                                
int a[N],b[N];
int n,m;
int cnt[1<<12];
vt state,head[1100];
ll f[12][110][1<<12];
bool check(int state){
    rep(i,0,n-1){
        if((state>>i&1)&&(state>>i+1&1))return false;
    }
    return true;
}
int calc(int state){
    int res=0;
    rep(i,0,n-1){
        if(state>>i&1)res++;
    }
    return res;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);  
    cout.tie(0);
    cin>>n>>m;
    rep(i,0,(1<<n)-1){
        if(check(i)){
            state.pb(i);
            cnt[i]=calc(i);
        }
    }
    rep(i,0,sz(state)-1){
        rep(j,0,sz(state)-1){
            int a=state[i];
            int b=state[j];
            if(!(a&b)&&check(a|b)){
                head[i].pb(j);
            }
        }
    }
    f[0][0][0]=1;
    rep(i,1,n+1){
        rep(j,0,m){
            rep(k,0,sz(state)-1){
                rep(l,0,sz(head[k])-1){
                    if(j>=cnt[state[k]])f[i][j][k]+=f[i-1][j-cnt[state[k]]][head[k][l]];
                }

            }
        }
    }
    cout<<f[n+1][m][0];

    return 0;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
using std::cout;
using std::cin;
using std::endl;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<ll> vt;
typedef set<int> st;
const int N=2e5+60;
const int mod=1e9+7;                                                
ll a[N],b[N];
int c[100][100];
int f[100010];
pii master[100];
vector<pii>servent[100];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    int t;
    cin>>n>>m;
    rep(i,1,m){
        int x,y,z;
        cin>>x>>y>>z;
        if(!z)master[i]={x,x*y};
        else servent[z].pb({x,x*y});
    }
    rep(i,1,m){
        per(j,n,0){
            rep(k,0,(1<<sz(servent[i]))-1){
                int v=master[i].fi;
                int w=master[i].se;
                rep(l,0,sz(servent[i])-1){
                    if(k>>l&1){
                        v+=servent[i][l].fi;
                        w+=servent[i][l].se;
                    }
                }
                if(j>=v)f[j]=max(f[j],f[j-v]+w);
            }

        }
    }
    cout<<f[n];



    return 0;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
using std::cout;
using std::cin;
using std::endl;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define all(c) (c).begin(),(c).end()
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))
#define srt(c) sort(all(c))
#define rev(c) reverse(all(c))
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<ll> vt;
typedef set<int> st;
const int N=2e5+60;
const int mod=1e9+7;                                                
ll a[N],b[N];
int c[100][100];
int f[10010];
struct cnt{
    int s,e,l;
}stone[N];
bool cmp(cnt x,cnt y){
    return x.s*y.l<x.l*y.s;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    int t;
    cin>>t;
    k=0;
    while(t--){
        int s,e,l;
        int m=0;
        memset(f,0,sizeof f);
        f[0]=0;
        cin>>n;
        rep(i,1,n){
            cin>>s>>e>>l;
            stone[i]={s,e,l};
            m+=s;
        }
        sort(stone+1,stone+n+1,cmp);
        rep(i,1,n){
            per(j,m,stone[i].s){
                f[j]=max(f[j],f[j-stone[i].s]+max(0,stone[i].e-(j-stone[i].s)*stone[i].l));
            }
        }
        int res=0;
        rep(i,0,m)res=max(res,f[i]);
        cout<<"Case #"<<++k<<": "<<res<<endl;
    }


    return 0;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define pb push_back
#define sz(v) ((int)(v.size()))
#define fi first
#define se second
typedef long long ll;
typedef double db; 
typedef pair<int,int> pii;
typedef vector<int> vt;
const int N=2e5+10;
const int mod=1e9+7;
int a[N],b[N];
int f[1030][1030],cnt[1030][1030];
int v[1030],w[1030];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    int t;
    cin>>n>>m;
    rep(i,1,n){
        cin>>v[i]>>w[i];
    }
    rep(i,0,m){
        cnt[0][i]=1;
    }
    rep(i,1,n){
        rep(j,0,m){
            if(j<v[i]){
                f[i][j]=f[i-1][j];
                cnt[i][j]=cnt[i-1][j];
                continue;
            }
            int res=f[i-1][j];
            int ans=f[i-1][j-v[i]]+w[i];
            f[i][j]=max(res,ans);
            if(res>ans)cnt[i][j]=cnt[i-1][j];
            else if(res<ans)cnt[i][j]=cnt[i-1][j-v[i]];
            else if(res==ans)cnt[i][j]=cnt[i-1][j]+cnt[i-1][j-v[i]];
            cnt[i][j]%=mod;
        }
    }
    cout<<cnt[n][m];


    return 0; 

}

题目描述

有 N
种物品和一个容量是 V
的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si
次（多重背包）；
每种体积是 vi
，价值是 wi
。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V
，用空格隔开，分别表示物品种数和背包容积。

接下来有 N
行，每行三个整数 vi,wi,si
，用空格隔开，分别表示第 i
种物品的体积、价值和数量。

si=−1
表示第 i
种物品只能用1次；
si=0
表示第 i
种物品可以用无限次；
si>0
表示第 i
种物品可以使用 si
次

样例

输入样例`
4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例
8

思路

统一转化为多重背包求解

C++ 代码

#import<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define pb push_back
#define sz(v) ((int)(v.size()))
#define fi first
#define se second
typedef long long ll;
typedef double db; 
typedef pair<int,int> pii;
typedef vector<int> vt;
const int N=2e5+10;
const int mod=1000000007;
int a[N],b[N];
int f[6050],v[5050],w[5050],s[5050];
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m,k;
    cin>>n>>m;
    rep(i,1,n){
        int x,y,g;
        cin>>x>>y>>g;
        v[i]=x;
        w[i]=y;
        if(g==-1)s[i]=1;//一次性物品的数量设为1
        else if(g==0)s[i]=m/v[i];//无限多物品的数量设为当前背包容量所能装下该物品的最大数量
        else s[i]=g;
    }
    //多重背包2dp
    rep(i,1,n){
       for(int k=1;s[i]>0;k<<=1){
           int x=min(k,s[i]);
           per(j,m,v[i]*x){
               f[j]=max(f[j],f[j-x*v[i]]+x*w[i]);
           }
           s[i]-=x;
       }
    }
    cout<<f[m];

    return 0; 

}

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<ll> vt;
const int N=2e7+60;
const int mod=1e8;    
ll c[N],k[N];
pii p[N];                                           
int n,m;
int INF=1e9+5;
int fa[N];
vector<int>g;
vector<pii>h;
struct cnt{
    int a,b;
    ll w;
    bool operator <(const cnt &g)const{
        return w<g.w;
    }
}e[N];
void init(){
    rep(i,1,n)fa[i]=i;
}
int find(int x){
    if(x!=fa[x])fa[x]=find(fa[x]);
    return fa[x];
}
int merge(int x,int y){
    int a=find(x);
    int b=find(y);
    if(a==b)return 0;
    fa[b]=a;
    return 1;
}
ll krustal(){
    ll ans=0;
    sort(e+1,e+m+1);
    rep(i,1,m){
        if(merge(e[i].a,e[i].b)){
            ans+=e[i].w;
            if(e[i].a==0)g.pb(e[i].b);
            else h.pb({e[i].a,e[i].b});
            n--;
            if(n==0)return ans;
        }
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);  
    cout.tie(0);
    cin>>n;
    rep(i,1,n){
        int x,y;
        cin>>x>>y;
        p[i]={x,y};
    }
    rep(i,1,n)cin>>c[i];
    rep(i,1,n)cin>>k[i];
    rep(i,1,n){
        e[++m]={0,i,c[i]};
    }
    rep(i,1,n){
        int x1=p[i].fi;
        int y1=p[i].se;
        rep(j,1,n){
            int x2=p[j].fi;
            int y2=p[j].se;
            e[++m]={i,j,ll((k[i]+k[j])*(abs(x1-x2)+abs(y1-y2)))};
        }
    }
    init();
    ll res=krustal();
    cout<<res<<endl;
    cout<<sz(g)<<endl;
    rep(i,0,sz(g)-1)cout<<g[i]<<' ';
    cout<<endl;
    cout<<sz(h)<<endl;
    for(auto [x,y] :h){
        cout<<x<<' '<<y<<endl;
    }


    return 0;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<ll> vt;
const int N=2e7+60;
const int mod=1e8;    
ll c[N],k[N];
pii p[N];                                           
int n,m;
int INF=1e9+5;
int fa[N];
vector<int>g;
vector<pii>h;
struct cnt{
    int a,b;
    ll w;
    bool operator <(const cnt &g)const{
        return w<g.w;
    }
}e[N];
void init(){
    rep(i,1,n)fa[i]=i;
}
int find(int x){
    if(x!=fa[x])fa[x]=find(fa[x]);
    return fa[x];
}
int merge(int x,int y){
    int a=find(x);
    int b=find(y);
    if(a==b)return 0;
    fa[b]=a;
    return 1;
}
ll krustal(){
    ll ans=0;
    sort(e+1,e+m+1);
    rep(i,1,m){
        if(merge(e[i].a,e[i].b)){
            ans+=e[i].w;
            if(e[i].a==0)g.pb(e[i].b);
            else h.pb({e[i].a,e[i].b});
            n--;
            if(n==0)return ans;
        }
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);  
    cout.tie(0);
    cin>>n;
    rep(i,1,n){
        int x,y;
        cin>>x>>y;
        p[i]={x,y};
    }
    rep(i,1,n)cin>>c[i];
    rep(i,1,n)cin>>k[i];
    rep(i,1,n){
        e[++m]={0,i,c[i]};
    }
    rep(i,1,n){
        int x1=p[i].fi;
        int y1=p[i].se;
        rep(j,1,n){
            int x2=p[j].fi;
            int y2=p[j].se;
            e[++m]={i,j,ll((k[i]+k[j])*(abs(x1-x2)+abs(y1-y2)))};
        }
    }
    init();
    ll res=krustal();
    cout<<res<<endl;
    cout<<sz(g)<<endl;
    rep(i,0,sz(g)-1)cout<<g[i]<<' ';
    cout<<endl;
    cout<<sz(h)<<endl;
    for(auto [x,y] :h){
        cout<<x<<' '<<y<<endl;
    }


    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<ll> vt;
const int N=2e5+60;
const int mod=1e8;                                               
int n,m;
int INF=1e9+5;
int g[600][600],dist[600],vis[600];
int prim(){
    int ans=0;
    rep(i,1,n){
        dist[i]=g[1][i];
    }
    dist[1]=0;
    vis[1]=1;
    rep(i,1,n){
        int temp=INF+1;
        int t=0;
        rep(j,1,n){
            if(!vis[j]&&dist[j]<temp){
                temp=dist[j];
                t=j;
            }
        }
        if(dist[t]==INF)return INF;
        ans+=dist[t];
        if(!t)break;
        vis[t]=1;
        rep(j,1,n){
            if(!vis[j]&&dist[j]>g[t][j]){
                dist[j]=g[t][j];
            }
        }
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);  
    cout.tie(0);
    cin>>n>>m;
    rep(i,1,n){
        rep(j,1,n){
            g[i][j]=INF;
        }
    }
    rep(i,1,m){
        int x,y,w;
        cin>>x>>y>>w;
        g[x][y]=g[y][x]=min(g[x][y],w);
    }
    int ans=prim();
    if(ans==INF)cout<<"impossible";
    else cout<<ans;

    return 0;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define sz(v) ((int)v.size())
#define pb push_back
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<ll> vt;
const int N=2e5+60;
const int mod=1e8;                                               
int n,m;
int INF=1e9+5;
int g[600][600],dist[600],vis[600];
int prim(){
    int ans=0;
    rep(i,1,n){
        dist[i]=g[1][i];
    }
    dist[1]=0;
    vis[1]=1;
    rep(i,1,n){
        int temp=INF+1;
        int t=0;
        rep(j,1,n){
            if(!vis[j]&&dist[j]<temp){
                temp=dist[j];
                t=j;
            }
        }
        if(dist[t]==INF)return INF;
        ans+=dist[t];
        if(!t)break;
        vis[t]=1;
        rep(j,1,n){
            if(!vis[j]&&dist[j]>g[t][j]){
                dist[j]=g[t][j];
            }
        }
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);  
    cout.tie(0);
    cin>>n>>m;
    rep(i,1,n){
        rep(j,1,n){
            g[i][j]=INF;
        }
    }
    rep(i,1,m){
        int x,y,w;
        cin>>x>>y>>w;
        g[x][y]=g[y][x]=min(g[x][y],w);
    }
    int ans=prim();
    if(ans==INF)cout<<"impossible";
    else cout<<ans;

    return 0;
}