dp模板大全（欢迎来补充）

· · 算法·理论

最大子段和：


#include<bits/stdc++.h>
using namespace std;
/*
dp[i]表示以第i个数结尾的最大字段和
dp[i]=max(dp[i],for(int j=i-1;j>=1;j--)dp[i]+a[j];
*/
const int N=2e5+100;
long long dp[N];
int a[N];
int max(long long k,long long l){
    if (k>l) return k;
    else return l;
}
int main(){
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    dp[1]=a[1];
    for (int i=2;i<=n;i++){
        dp[i]=max(dp[i-1]+a[i],a[i]);
    }
    long long ans=LLONG_MIN;
    for (int i=1;i<=n;i++) ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

01 背包:

const int N=1e5+100;
int n, m, w[N], v[N], dp[N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
    cout << dp[m];
}

完全背包:

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

多重背包:

cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> c[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c[i]; j <<= 1) w1[++n1] = w[i] * j, v1[n1] = v[i] * j, c[i] -= j;
        if (c[i]) w1[++n1] = w[i] * c[i], v1[n1] = v[i] * c[i];
    }
    for (int i = 1; i <= n1; i++) {
        for (int j = m; j >= w1[i]; j--) dp[j] = max(dp[j], dp[j - w1[i]] + v1[i]);
    }
    cout << dp[m];

分组背包:

for (int k = 1; k <= y; k++) {
            for (int j = s; j >= 0; j--) {
                for (int i = 1; i <= cnt[k]; i++) {
                    int idx = f[k][i];
                    if (j >= w[idx]) dp[j] = max(dp[j], dp[j - w[idx]] + v[idx]);
                }
            }
        }

求最长上升子序列长度

 // 求最长上升子序列长度
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(a[j]<a[i]){ // 如果满足递增要求就更新
                dp1[i] = max(dp1[i],dp1[j]+1); // 判断拼接转移后长度是否更长
            }
        }
    }

求最长下降子序列长度，我们可以反着找

 for(int i=n;i>0;i--){
        for(int j=n+1;j>i;j--){
            if(a[j]<a[i]){
                dp2[i]=max(dp2[i],dp2[j]+1); // 判断拼接转移后长度是否更长
            }
        }
    }

未完成