CSP-J精英营 day6 笔记

ebzyl · 2023-07-14 10:30:24 · 个人记录

上午

一、背包

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int n,m;
int f[maxn][maxn];
int v[maxn],w[maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            f[i+1][j]=max(f[i+1][j],f[i][j]);
            f[i+1][j+v[i+1]]=max(f[i][j],f[i+1][j]+w[i+1]);
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
    return 0;
} 

二、无穷背包

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int n,m;
int f[maxn][maxn];
int v[maxn],w[maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k*v[i]<=j;k++){
                f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i],f[i][j]);   
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
    return 0;
} 

三、有限背包

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int n,m;
int f[maxn][maxn];
int v[maxn],w[maxn],z[maxn];
int main(){
    cin>>n>>m;
    int cnt=0; 
    int v_,w_,k_;
    for(int i=1;i<=n;i++){
        cin>>v_>>w_>>k_;
        int x=1;
        while(k_>=x){
            cnt++;
            v[cnt]=v_*x;
            w[cnt]=w_*x;
            k_-=x;
            x=x<<1;
        }
        if(k_!=0){
            cnt++;
            v[cnt]=v_*k_;
            w[cnt]=w_*k_;
        }
    }
    n=cnt;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k*v[i]<=j&&k<=z[i];k++){
                f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i],f[i][j]);   
            }
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
    return 0;
} 

四、背包——滚动数组

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int n,m;
int f[2][maxn];
int v[maxn],w[maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=0;i<n;i++){
        int p=(i&1);
        int q=(p^1);
        memset(f[q],0,sizeof(f[q]));
        for(int j=0;j<=m;j++){
            f[q][j]=max(f[q][j],f[p][j]);
            f[q][j+v[i+1]]=max(f[p][j],f[q][j]+w[i+1]);
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,f[n&1][i]);
    }
    cout<<ans;
    return 0;
} 

五、区间DP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int n;
int a[maxn];
int sum[maxn];
int f[maxn][maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++){
        f[i][i]=0;
    } 
    for(int len=2;len<=n;len++){
        for(int l=1,r=len;r<=2*n;l++,r++){
            for(int k=l;k<r;k++){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    int ans1=0x3f3f3f3f,ans2=-1;
    for(int i=1;i<=n;i++){
        ans1=min(ans1,f[i][i+n-1]);
        ans2=max(ans2,f[i][n]);
    }
    cout<<ans1<<'\n'<<f[1][n];
    return 0;
}