RQNOJ 石子合并

点击打开链接

思路: 区间dp
分析:
1 很多人可能看到这一题首先想到的是贪心，但是很不幸的是这道题的贪心做法是错误的，因此正解是dp
2 不管怎么合并，总之最后总会归结为2堆，如果我们把最后的两堆分开，左边和右边无论怎么合并都必须满足最优合并方案，整个问题才能是最优的
3 题目是一个环，我们可以把环变成链那就是在后面在加上去，那么最后的ans一定是dp[1][n-1]，dp[2][n]...中的最小值和最大值
4 我们dpMin[i][j]表示合并第i堆到第j堆石子所得的最小分数，dpMax[i][j]表示最大分数。sum[i]表示从1～i堆石子的分数总和
5 很容易得到状态转移方程
dpMin[i][j] = min(dp[i][j] , dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
dpMax[i][j] = max(dp[i][j] , dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1<<30;
const int N = 210;
int n;
int num[N] , sum[N];
int dpMax[N][N] , dpMin[N][N];

void init(){
    memset(sum , 0 , sizeof(sum));
    for(int i = 1 ; i <= 2*n ; i++){
        dpMax[i][i] = dpMin[i][i] = 0;
        sum[i] = sum[i-1]+num[i];;
    }
}

void solve(){
    for(int k = 1 ; k < n ; k++){//枚举区间的长度
        for(int i = 1 ; i <= 2*n-k ; i++){//区间的左端点
            int j = i+k;//区间的右端点
            dpMax[i][j] = -INF;
            dpMin[i][j] = INF;
            //枚举区间的剖分点
            for(int p = i ; p < j ; p++){
                int score = sum[j]-sum[i-1];
                dpMax[i][j] = max(dpMax[i][j],dpMax[i][p]+dpMax[p+1][j]+score);
                dpMin[i][j] = min(dpMin[i][j],dpMin[i][p]+dpMin[p+1][j]+score);
            }
        }
    }
    int minSco = INF;
    int maxSco = -INF;
    for(int i = 1 ; i <= n ; i++){
        minSco = min(minSco , dpMin[i][i+n-1]); //注意区间长度为n那么右端点是i+n-1
        maxSco = max(maxSco , dpMax[i][i+n-1]); 
    }
    printf("%d\n%d\n" , minSco , maxSco);
}

int main(){
    while(scanf("%d" , &n) != EOF){
         for(int i = 1 ; i <= n ; i++){
             scanf("%d" , &num[i]); 
             num[i+n] = num[i];
         }
         init();
         solve();
    }
    return 0;
}