AcWing 2. 01背包问题

#include<iostream>
using namespace std;
const int maxn=2e6;
int v[maxn],w[maxn];
int value[maxn];//val: ans, i:i-st goods,   j:volumn
//value[i][j]=max(value[i-1][j],value[i-1][j-v[i]]+w[i]) for all j
int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=V;j>=v[i];j--)
            value[j]=max(value[j],value[j-v[i]]+w[i]);
    }
    cout<<value[V];
}

AcWing 893. 集合-Nim游戏

下标写错i~k, x~f[x]，吐了

#include<iostream>
#include<unordered_set>
using namespace std;
const int maxn=(int)1e5+5;
int s[maxn],mn,f[maxn];
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
int k;
int sg(int x){
    if(f[x]!=-1)return f[x];
    unordered_set<int> st;
    rep(i,1,k)if(x-s[i]>=0)st.insert(sg(x-s[i]));
    for(int i=0;;i++)if(!st.count(i)){return f[x]=i;}
}
int main(){
    cin>>k;

    rep(i,1,maxn-1)f[i]=-1;
    rep(i,1,k)cin>>s[i];
    int n;cin>>n;
    int res=0;
    while(n--){int x;cin>>x;res^=sg(x);}
    //rep(x,0,7)cout<<(sg(x))<<' '<<(x)<<endl;
    cout<<(res?"Yes":"No")<<endl;
}

完全背包

#include<iostream>
using namespace std;
const int maxn=1005;
int v[maxn],w[maxn],value[maxn];

int main(){
    int n,vv;
    cin>>n>>vv;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int cnt=1;cnt*v[i]<=vv;cnt++)
            for(int j=vv;j>=cnt*v[i];j--){
                value[j]=max(value[j],value[j-cnt*v[i]]+cnt*w[i]);
            }
    }
    cout<<value[vv]<<endl;
}

#include<iostream>
using namespace std;
const int maxn=1005;
int v[maxn],w[maxn],value[maxn];

int main(){
    int n,vv;
    cin>>n>>vv;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
            for(int j=v[i];j<=vv;j++){
                value[j]=max(value[j],value[j-v[i]]+w[i]);
            }
    }
    cout<<value[vv]<<endl;
}

AcWing 9. 分组背包问题

reflection
多重背包，一个是二进制优化思想和实现， 第二是倒着更新，for体积要放在外层（第二层）
分组背包也一样， 如果二维数组需要每次把上一行复制下来

#include<iostream>
using namespace std;
const int maxn=105;
int v[maxn][maxn],w[maxn][maxn],value[maxn][maxn],m[maxn];
//can't reverse update.
//update value[i][j]
int main(){
    int n,vv;
    cin>>n>>vv;
    for(int i=1;i<=n;i++){
        cin>>m[i];
        for(int j=1;j<=m[i];j++){
           cin>>v[i][j]>>w[i][j]; 
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m[i];j++){

            for(int k=v[i][j];k<=vv;k++){
                //value[i][k]=max(value[i][k],value[i-1][k]); 这句话是错地，要把v的第i-1行全复制到i行，所以上面j从0开始
                value[i][k]=max(value[i][k],value[i-1][k-v[i][j]]+w[i][j]);
            }
        } 
    }
    /*for(int i=1;i<=n;i++){
        for(int k=vv;k>=0;k--)//这种写法要先枚举k，否则限制就没了
            for(int j=1;j<=m[i];j++)if(k-v[i][j]>=0){ 
                value[n][k]=max(value[n][k],value[n][k-v[i][j]]+w[i][j]);
        }

    }*/
    cout<<value[n][vv]<<endl;

}

AcWing 898. 数字三角形

边界

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=505;
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
int a[maxn][maxn],dp[maxn][maxn];
void checkmx(int& a,int b){
    if(b>a)a=b;
}
int main(){
    int n;cin>>n;
    rep(i,1,n)rep(j,1,i)cin>>a[i][j];

    dp[1][1]=a[1][1];
    rep(i,2,n)rep(j,1,i){
        dp[i][j]=-100000;
        if(i-1>=j)checkmx(dp[i][j],dp[i-1][j]);
        if(j-1>0 )checkmx(dp[i][j],dp[i-1][j-1]);
        dp[i][j]+=a[i][j];
        //cout<<dp[i][j]<<' ';
    }

    cout<<*max_element(dp[n]+1,dp[n]+1+n)<<endl;
}

AcWing 895. 最长上升子序列

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
int a[maxn],last[maxn];// key:length, val:smallest
void checkmx(int& a,int b){
    if(b>a)a=b;
}
int main(){
    int n;cin>>n;
    rep(i,1,n)cin>>a[i];
    int len=0;
    rep(i,1,n){
        int p=lower_bound(last+1,last+1+len,a[i])-last;
        last[p]=a[i];    
        len=max(len,p);
    }

    cout<<len<<endl;
}

AcWing 897. 最长公共子序列

reflection:
边界，i=1 loop
输出一组解：画出表格，每次相等时往左上角移动，否则沿着与当前相同的dp值移动

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn=1005;
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
int a[maxn],dp[maxn][maxn];//
void checkmx(int& a,int b){
    if(b>a)a=b;
}
int main(){
    int n,m;cin>>n>>m;
    string s,ss;cin>>s>>ss;
    rep(i,1,n)rep(j,1,m){
        checkmx(dp[i][j],dp[i-1][j]);
        checkmx(dp[i][j],dp[i][j-1]);
        checkmx(dp[i][j],dp[i-1][j-1]+(s[i-1]==ss[j-1]));
    }

    cout<<dp[n][m]<<endl;
}

AcWing 902. 最短编辑距离

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn=1005;
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
int a[maxn],dp[maxn][maxn];//
void checkmn(int& a,int b){
    if(b<a)a=b;
}
int main(){
    int n,m;
    string s,ss;cin>>n>>s>>m>>ss;
    rep(i,1,n)dp[i][0]=i;
    rep(i,1,m)dp[0][i]=i;
    //puts("1");
    rep(i,1,n)rep(j,1,m){

        dp[i][j]=1e4;
        checkmn(dp[i][j],dp[i-1][j]+1);
        checkmn(dp[i][j],dp[i][j-1]+1);
        checkmn(dp[i][j],dp[i-1][j-1]+!(s[i-1]==ss[j-1]));
        //cout<<dp[i][j]<<' ';

    }

    cout<<dp[n][m]<<endl;
}

AcWing 282. 石子合并

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn=1005;
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
int a[maxn],dp[maxn][maxn];//
void checkmn(int& a,int b){
    if(b<a)a=b;
}
int main(){
    int n;
    cin>>n;
    rep(i,1,n)cin>>a[i],a[i]+=a[i-1];
    rep(len,2,n)rep(l,1,n){//len=1没有花费
        int r=l+len-1;
        dp[l][r]=1e9;//max=300*300*1000
        rep(k,l,r-1){
            checkmn(dp[l][r],dp[l][k]+dp[k+1][r]+a[r]-a[l-1]);
        }
    }

    cout<<dp[1][n]<<endl;
}

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int maxn=1005;

define int long long

const int mod=(int)1e9+7;

define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)

int a[maxn],dp[maxn];//
void checkmn(int& a,int b){
if(b[HTML_REMOVED]>n;
dp[0]=1;
rep(i,1,n){
rep(j,1,n){
dp[j]+=dp[j-i];
dp[j]%=mod;
}
}

cout<<dp[n]<<endl;

}