区间DP模型

区间 DP 常用模版

所有的区间dp问题，第一维都是枚举区间长度，一般 len = 1 用来初始化，枚举从 len = 2 开始，第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）

for (int i = 1; i <= n; i++) {
    dp[i][i] = 初始值
}
for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
        int j = i + len - 1;                 //区间终点
        for (int k = i; k < j; k++) {        //枚举分割点，构造状态转移方程
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }

1068. 环形石子合并

https://www.acwing.com/problem/content/1070/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
int n;
int a[500];
int fmax[500][500];
int fmin[500][500];
const int INF=0x3f3f3f3f;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    memset(fmax,-INF,sizeof(fmax));
    memset(fmin,INF,sizeof(fmin));
    for(int i=1;i<=2*n;i++){
        a[i]+=a[i-1];
        fmax[i][i]=0;
        fmin[i][i]=0;
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=2*n;l++){
            int r=l+len-1;
            for(int k=l;k<r;k++){
                fmax[l][r]=max(fmax[l][r],fmax[l][k]+fmax[k+1][r]+a[r]-a[l-1]);
                fmin[l][r]=min(fmin[l][r],fmin[l][k]+fmin[k+1][r]+a[r]-a[l-1]);
            }
        }
    }
    int minv = INF , maxv = -INF;
        for(int i = 1; i <= n;i++)
        {
            minv = min(minv, fmin[i][i + n - 1]);
            maxv = max(maxv, fmax[i][i + n - 1]);
        }
     cout << minv << endl << maxv << endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

320. 能量项链

https://www.acwing.com/problem/content/322/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
int n;
int a[250];
int f[250][250];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int len=3;len<=n+1;len++){
        for(int i=1;i+len-1<=2*n;i++){
            int j=i+len-1;
            for(int k=i+1;k<j;k++){
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i){
         ans = max(ans, f[i][i + n]); 
    }

    cout << ans << endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

479. 加分二叉树

https://www.acwing.com/problem/content/description/481/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50;

int n;
int w[N];
unsigned f[N][N];
int root[N][N];

void dfs(int l, int r)
{
    if (l > r) return;

    int k = root[l][r];
    printf("%d ", k);
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int len = 1; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;

            for (int k = l; k <= r; k ++ )
            {
                int left = k == l ? 1 : f[l][k - 1];
                int right = k == r ? 1 : f[k + 1][r];
                int score = left * right + w[k];
                if (l == r) score = w[k];
                if (f[l][r] < score)
                {
                    f[l][r] = score;
                    root[l][r] = k;
                }
            }
        }

    printf("%d\n", f[1][n]);
    dfs(1, n);
    puts("");

    return 0;
}

区间DP模型

原文：https://www.cnblogs.com/OfflineBoy/p/14774067.html