动态规划-洛谷P1880

题目链接

落谷P1880

思路

dp[i][j]表示第i~j个石子合并的最小花费得到转移方程

$$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);$$

因为i~j需要从i~(j-1)的所有状态推出，所以先枚举i，在枚举j,最后枚举k，保证所有状态都转移到，然后成环就让数列*2就好了

代码实现

/*
 * link: https://loj.ac/problem/10147 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 500;
int a[N];
ll sum[N];
ll dp[N][N];
ll mdp[N][N];
int main(){
    int n;
    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 len = 1;len<=n;len++){
        for(int i=1;i<=2*n-1;i++){
            int j = len+i;
            mdp[i][j]=1e9+10;
            for(int k=i;k<j&&k<=2*n-1;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
                mdp[i][j]=min(mdp[i][j],mdp[i][k]+mdp[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    ll ansx = 0;
    ll ansm = 1e9+10;
    for(int i=1;i<=n;i++){
        ansx = max(ansx,dp[i][i+n-1]);
        ansm = min(ansm,mdp[i][i+n-1]);
    }
    printf("%lld\n%lld\n",ansm,ansx);
}