[区间DP] P1880 [NOI1995] 石子合并 P1063 能量项链

关于区间DP的额外链接 https://blog.csdn.net/qq_40831340/article/details/83478132
北京2014 icpc https://blog.csdn.net/qq_40831340/article/details/82714715

题目 石子合并 题目链接 https://www.luogu.org/problemnew/show/P1880

dp[i][j] 表示i-j区间的合并最优解
dp[i][j]={可以合并的区间+当前合并的代价}

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

由于是环状的 只要把数组拉长 重复之前的即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <list> 
using namespace std;
typedef long long ll;

const int maxn = 200+5 ;
const int maxv = 10000+5;
const int mod = 1000000 ;
const int INF = 0x3f3f3f3f;
const double PI=acos(-1.0);

int n,m;
int a[maxn],sum[maxn];
int dp1[maxn][maxn],dp2[maxn][maxn];

int dsum(int l,int r){
    return sum[r]-sum[l-1];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
    for(int pj=1;pj<n;pj++){
    	for(int i=1,j=i+pj;i<n*2&&j<n*2;i++,j++){
    		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]+dsum(i,j));
    			dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+dsum(i,j));
            }
        }
    }
    int mians=INF,maxans=0;
    for(int i=1;i<=n;i++){
        mians=min(dp1[i][n+i-1],mians);
        //cout<<mians<<endl;
        maxans=max(maxans,dp2[i][i+n-1]);
    }
    cout<<mians<<endl<<maxans<<endl;
    return 0;
}

题目2 链接 https://www.luogu.org/problemnew/show/P1063

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <list> 
using namespace std;
typedef long long ll;

const int maxn = 200+5 ;
const int maxv = 10000+5;
const int mod = 1000000 ;
const int INF = 0x3f3f3f3f;
const double PI=acos(-1.0);

int n,m,p,cmd,x,y,k;

int dp[maxn][maxn];
int l[maxn],r[maxn];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i],r[i-1]=l[i];
    r[n]=l[1];
    for(int i=1;i<n;i++) l[i+n]=l[i],r[i+n]=r[i];
    
    for(int jg=1;jg<=n;jg++){
        for(int i=1;i<2*n-jg;i++){
            int j=i+jg;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+l[i]*l[k+1]*r[j]);     
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,dp[i][i+n-1]);
    cout<<ans<<endl;
    return 0;
}

区间dp能解决的问题就是通过小区间更新大区间，最后得出指定区间的最优解