首页 > 编程语言 >算法基础模板整理（动态规划篇）

算法基础模板整理（动态规划篇）

时间：2023-04-14 13:56:25浏览次数：46  
标签：idx int max cin -- 算法 模板 动态 dp

背包问题

01背包问题

static const int N = 1010;
int dp[N][N], v[N], w[N], n, c;

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

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

    return 0;
}

int dp[N], v[N], w[N], n, c;

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = c; j >= v[i]; j -- )    //需要倒序 
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]); //保证是从上一层的数据过来的
    //如果正序 对于某个容量j，小于j的容量的dp值已经被更新，此时已经不再是上一层的了
    cout << dp[c];

    return 0;
}

完全背包问题

static const int N = 1010;
int dp[N][N], v[N], w[N], n, c;

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= c; j ++ ){
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    /*
    dp[i][j] =       max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2 * v] + 2 * w ... )
    dp[i][j - v] =   max(              dp[i - 1][j - v],     dp[i - 1][j - 2 * v] + w     ... )
    所以
    dp[i][j] =       max(dp[i - 1][j], dp[i][j - v] + w)  
    */
    cout << dp[n][c];

    return 0;
}

//一维数组版本
int dp[N], v[N], w[N], n, c;

int main(){
    cin >> n >> c;
    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 <= c; j ++ )
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[c];

    return 0;
}

分组背包问题

static const int N = 110;
int dp[N], v[N], w[N];
int n, c;

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; i ++ ){
        int cnt; cin >> cnt;
        for(int j = 1; j <= cnt; j ++ ) cin >> v[j] >> w[j];
        for(int j = c; j >= 0; j -- )
            for(int k = 1; k <= cnt; k ++ )      //对于每个容量 每组只能选择一个 所以外循环为容量 内循环为物品
                if(j >= v[k]) dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
    }

    cout << dp[c];

    return 0;
}

多重背包

const int N = 110;
int dp[N], n, c;

int main(){
    cin >> n >> c;
    int v, w, s;
    while(n -- ){
        cin >> v >> w >> s;
        for(int j = c; j >= 0; j -- )
            for(int k = 0; k <= s && k * v <= j; k ++ )
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
    }
    cout << dp[c];
}

二维费用背包问题

const int N = 110;
int dp[N], n, c;

int main(){
    cin >> n >> c;
    int v, w, s;
    while(n -- ){
        cin >> v >> w >> s;
        for(int j = c; j >= 0; j -- )
            for(int k = 0; k <= s && k * v <= j; k ++ )
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
    }
    cout << dp[c];
}

混合背包问题

#include<iostream>
using namespace std;

const int N = 1010;
int n, c, v, w, s;
int dp[N];

int main(){
    cin >> n >> c;
    while(n -- ){
        cin >> v >> w >> s;
        if(!s){
            for(int j = v; j <= c; j ++ )
                dp[j] = max(dp[j], dp[j - v] + w);
        }else if(s){
            if(s == -1) s = 1;
            for(int k = 1; k <= s; k <<= 1){
                for(int j = c; j >= k * v; j -- )
                    dp[j] = max(dp[j], dp[j - k * v] + k * w);
                s -= k;
            }
            if(s){
                for(int j = c; j >= s * v; j -- )
                    dp[j] = max(dp[j], dp[j - s * v] + s * w);
            }
        }
    }

    cout << dp[c] << endl;

    return 0;
}

数字三角形模型

for(int j = 0; j < n; j++)
    dp[n - 1][j] = a[n - 1][j];
for(int i = n - 2; i >= 0; i--)
    for(int j = 0; j < n; j++)
        dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];

cout << dp[0][0];

子序列

最长上升子序列模型

int ans = 0;
for(int j = 1; j <= n; j++){
    dp[j] = 1;
    for(int i = 1; i < j; i++){
        if(a[i] < a[j])
            dp[j] = max(dp[j], dp[i] + 1);
    }
    ans = max(ans, dp[j]);
}
cout << ans;

最长公共子序列模型

for(int i = 1; i <= n; i ++ )
    for(int j = 1; j <= m; j ++ )
        if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
cout << dp[n][m];

最长公共上升子序列模型

for(int i = 1; i <= n; i ++ ){
    int maxv = 1;
    for(int j = 1; j <= n; j ++ ){   //枚举结尾
        dp[i][j] = dp[i - 1][j];
        if(a[i] == b[j]) dp[i][j] = max(dp[i][j], maxv);
        if(a[i] > b[j]) maxv = max(maxv, dp[i - 1][j] + 1);
    }
}

int res = 0;
for(int i = 1; i <= n; i ++ ) res = max(res, dp[n][i]);
cout << res;

子序列匹配个数模型

for(int i = 0; i <= m; i ++ ) dp[i][n] = 1;
        for(int i = m - 1; i >= 0; i -- )
            for(int j = n - 1; j >= 0; j -- )
                if(s[i] == t[j]) dp[i][j] = (dp[i + 1][j + 1] + dp[i + 1][j]) % mod;
                else dp[i][j] = dp[i + 1][j] % mod;
        
        cout << dp[0][0] % mod << endl;

最大子段和模型

cin >> n;
        for(int i = 1; i <= n; i ++ ) cin >> a[i];

        sum = 0;
        for(int i = 1; i <= n; i ++ )   //最大子段和模型
            sum = max(0, sum) + a[i], dp1[i] = max(dp1[i - 1], sum);

        sum = 0;
        for(int i = n; i; i -- ) 
            sum = max(0, sum) + a[i], dp2[i] = max(dp2[i + 1], sum);

区间DP

石子合并模型

cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
for(int len = 2; len <= n; len ++ ){
    for(int i = 1; i + len - 1 <= n; i ++ ){
        int j = i + len - 1;
        dp[i][j] = INT_MAX;
        for(int k = i; k < j; k ++ )
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
    }
}
cout << dp[1][n];

环形石子合并模型

cin >> n;
for(int i = 1; i <= n; i ++ ){
    cin >> a[i];
    a[n + i] = a[i];    //化环为链
}

for(int i = 1; i <= 2 * n - 1; i ++ ) pre[i] = pre[i - 1] + a[i];

for(int len = 1; len <= n; len ++ ){
    for(int i = 1; i <= 2 * n - len - 1; i ++ ){
        int j = i + len;
        dp1[i][j] = inf;
        for(int k = i; k < j; k ++ ){
            dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + pre[j] - pre[i - 1]);
            dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + pre[j] - pre[i - 1]);
        }
    }
}   

int resmin = inf, resmax = 0;
for(int i = 1; i <= n; i ++ ){
    resmin = min(resmin, dp1[i][i + n - 1]);
    resmax = max(resmax, dp2[i][i + n - 1]);
}

cout << resmin << endl << resmax;

环形石子合并模型 + 最优分割点标记

for(int i = 1; i <= n; i ++ ){
    cin >> a[i];
    a[n + i] = a[i];
    s[i][i] = i, s[n + i][n + i] = n + i;
    dp[i][i] = dp[n + i][n + i] = 0;
}

for(int i = 1; i <= 2 * n; i ++ ) pre[i] = pre[i - 1] + a[i];

for(int len = 1; len <= n; len ++ ){
   for(int i = 1; i <= 2 * n - len; i ++ ){
      int j = i + len;
      for(int k = s[i][j - 1]; k <= s[i + 1][j]; k ++ ){
          if(dp[i][j] > dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1]){
              dp[i][j] = dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1];
              s[i][j] = k;
          }
      }
   }
}

int res = 1 << 30;
for(int i = 1; i <= n + 1; i ++ )
    res = min(res, dp[i][i + n - 1]);
cout << res << endl;

记忆化搜索

典型示例 滑雪

const int N = 310;
int n, m, f[N][N], g[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int dp(int i, int j){
    int &v = f[i][j];
    if(v != -1) return v;

    v = 1;
    for(int k = 0; k < 4; k ++ ){
        int ni = i + dx[k], nj = j + dy[k];
        if(ni >= 1&& ni <= n&& nj >= 1&& nj <= m && g[ni][nj] < g[i][j])
            v = max(v, dp(ni, nj) + 1);
    }
    return v;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            cin >> g[i][j];

    memset(f, -1, sizeof(f));
    int ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            ans = max(ans, dp(i, j));

    cout << ans;
}

状态压缩DP

//状态压缩DP + 滚动数组优化（Acwing 4406.积木画）

typedef long long ll;
static const int mod = 1e9 + 7;
ll dp[2][3];  //dp[i][j]表示前i列填满并且填了第i+1列j个位置的方案
//第i种状态只与i-1有关，可以用滚动数组优化

int main(){
    int n; cin >> n;
    dp[1][0] = 1, dp[1][1] = 2, dp[1][2] = 1;
    
    for(int i = 2; i <= n; i ++ ){
        dp[i & 1][0] = (dp[i - 1 & 1][0] + dp[i - 1 & 1][2]) % mod;
        dp[i & 1][1] = (dp[i - 1 & 1][0] * 2 + dp[i - 1 & 1][1]) % mod;
        dp[i & 1][2] = (dp[i - 1 & 1][0] + dp[i - 1 & 1][1]) % mod;
    }
    
    cout << dp[n & 1][0] << endl;
}

树形DP

没有上司的舞会 模型

const int N = 6010;
int happy[N], n;
int h[N], e[N], ne[N], idx;
int dp[N][2];   //dp[u][0]表示在以u为根的子树中选择并且不选u，dp[u][1]表示...并且选择u
bool hasfa[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u){
    dp[u][1] = happy[u];

    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);

        dp[u][0] += max(dp[j][0], dp[j][1]);
        dp[u][1] += dp[j][0];
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> happy[i];

    memset(h, -1, sizeof(h));
    for(int i = 0; i < n - 1; i ++ ){
        int a, b; cin >> a >> b;
        hasfa[a] = true;
        add(b, a);
    }

    int root = 1;
    while(hasfa[root]) root++;

    dfs(root);

    cout << max(dp[root][0], dp[root][1]);
}

树上最远距离 模型

static const int N = 10010, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int dp[N][2];  //dp[i][0]表示i出发的最长路，dp[i][1]表示i出发的次长路
int n;
int res = -1e9;

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

void dfs(int u, int fa){
    dp[u][0] = dp[u][1] = 0;
    for(int i = h[u]; i != -1; i = ne[i]){
        int v = e[i], c = w[i];
        if(v == fa) continue;

        dfs(v, u);   //自底向上

        if(dp[v][0] + c > dp[u][0]) dp[u][1] = dp[u][0], dp[u][0] = dp[v][0] + c;
        else if(dp[v][0] + c > dp[u][1]) dp[u][1] = dp[v][0] + c;
    }

    res = max(res, dp[u][0] + dp[u][1]);
}

int main(){
    cin >> n;
    memset(h, -1, sizeof(h));
    for(int i = 1; i <= n - 1; i ++ ){
        int u, v, c; cin >> u >> v >> c;
        add(u, v, c), add(v, u, c);
    }

    dfs(1, -1);

    cout << res;

    return 0;
}

树上最大和模型

static const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], w[N], idx;
int n;
typedef long long ll;
ll dp[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa){
    dp[u] = (ll)w[u];
    for(int i = h[u]; i != -1; i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        dfs(v, u);   //自底向上
        dp[u] += max(0LL, dp[v]);
    }
}

int main(){
    memset(h, -1, sizeof(h));
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> w[i];
    for(int i = 1; i <= n - 1; i ++ ){
        int u, v; cin >> u >> v;
        add(u, v), add(v, u);
    }

    dfs(1, -1);

    ll res = -1e12;
    for(int i = 1; i <= n; i ++ ) res = max(res, dp[i]);

    cout << res;

    return 0;
}

标签：idx,int,max,cin,--,算法,模板,动态,dp
From： https://www.cnblogs.com/MAKISE004/p/17318072.html

相关文章

  • 字符串匹配算法KMP
    KMP算法是字符串的匹配算法，比如我给一个名为《文本》的字符串，和一个名为《样板》的字符串，询问《样板》在《文本》中出现过的次数，这就需要字符串匹配算法。对于匹配，形象一点可以看例子：《文本1》="abcdefghigklmn"《样板1》="abc"=============================《文本2》="abcde......
  • 算法基础模板整理（基础图论篇）
    拓扑排序bool topo(){    queue<int> q;    for(int u = 1; u <= n; u ++ )        if(!ind[u]) q.push(u);        int cnt = 0;    while(!q.empty()){        int u = q.front();        q.pop(); ......
  • 算法基础模板整理（高阶数据结构篇）
    树状数组动态区间和询问+点修改int lowbit(int x){    return x & -x;}void add(int x, int v){    for(int i = x; i <= n; i += lowbit(i)) tree[i] += v;}int query(int x){    int res = 0;    for(int i = x; i......
  • Java SpringBoot 中，动态执行 bean 对象中的方法
    根据不同的条件，调用不同的bean对象，执行对象中的方法SpringUtils工具类packagecom.vipsoft.web.utils;importcn.hutool.core.util.ArrayUtil;importorg.springframework.aop.framework.AopContext;importorg.springframework.beans.BeansException;importorg.sprin......
  • 栈应用——逆波兰算法
    个人主页：【......
  • 动态规划——经典问题的实现（Python）
    动态规划（dunamicprogramming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。将复杂的多段决策问题分解为若干相互关联的子决策问题以获得最优决策序列的方法，是由美国数学家贝尔曼(R.E.Bellman)于20世纪50年代提出，它的基本原理是贝尔曼在《动态规划》(1957年)一书中所提出的最......
  • 使用Spring的getBeansOfType实现接口多实现类的动态调用
     背景org.springframework.beans及org.springframework.context这两个包是SpringIoC容器的基础，其中重要的类有BeanFactory，BeanFactory是IoC容器的核心接口，其职责包括：实例化、定位、配置应用程序中的对象及建立这些对象间的依赖关系。ApplicationContext作为BeanFactory的子类......
  • MATLAB代码：基于条件风险价值的合作型Stackerlberg博弈微网动态定价与优化调度
    MATLAB代码：基于条件风险价值的合作型Stackerlberg博弈微网动态定价与优化调度注意：店主有大量P2P分布式交易以及纳什议价的代码，欢迎咨询关键词：微网优化调度条件风险价值合作博弈纳什谈判参考文档：《AcooperativeStackelberggamebasedenergymanagementconsideringpric......
  • 人工智能技术的最新进展：机器学习算法的应用与优化
    ​ 人工智能技术的不断发展，机器学习算法已经成为了人工智能领域的重要组成部分。机器学习算法是一种通过数据训练模型，从而使计算机能够自动学习和改进的技术。在过去的几年中，机器学习算法已经在各个领域得到了广泛的应用，包括自然语言处理、图像识别、智能推荐等。在机器学习算法......
  • MATLAB代码：基于模型预测算法的含储能微网双层能量管理模型 模型预测控制 MPC
    MATLAB代码：基于模型预测算法的含储能微网双层能量管理模型   模型预测控制 MPC关键词：储能优化模型预测控制MPC微网优化调度能量管理 参考文档：《ATwo-layerEnergyManagementSystemforMicrogridswithHybridEnergyStorageconsideringDegradationCosts》完......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99