题解 P1880 【[NOI1995]石子合并】

· · 题解

【思路】

区间DP

【核心思路】

又是围成一个圈
所以处理方式很显然
就是在原来的序列后面放一个和原来序列一样的序列就可以了
这样2-n+1区间就是存在的
而且是那1-n个数
就是起点不同而已
每次合并后的值等于原来合并的价值
加上
这次合并的石子数
如果只用一个二维数组f[i][j]的话显然是没有办法保存的
所以可以利用一个很优美的东西
前缀和
利用前缀和可以求出某个区间的石子数
也就是可以知道每次石子合并可以新得到的值
那么就可以只用f[i][j]来存i-j区间内
合并石子的最值就好了

【DP式】

DP方程式：
f1[i][j] = max(f1[i][j],f1[i][k] + f1[k + 1][j] + cost[i][j])
f2[i][j] = min(f2[i][j],f2[i][k] + f2[k + 1][j] + cost[i][j])
（一个求区间最大值，一个求区间最小值）
这个区间的最值就等于分成两个小区间合并起来之后的最值

【最终结果】

最后结果
自然是比较i-i + n - 1这个区间啦
因为圈不同于一条线的就是可以任选起点
所以要比较以每一个作为起点时的最值
输出就好了

【完整代码】

#include<iostream>
#include<cstdio>

using namespace std;
const int Max = 206;
int f1[Max][Max];
int f2[Max][Max];
int a[Max];
int sum[Max];
int cost[Max][Max];
int main()
{
    int n;
    cin >> n;
    for(register int i = 1;i <= n;++ i)
        cin >> a[i],a[i + n] = a[i];
    for(register int i = 1;i <= n * 2;++ i)
        sum[i] = sum[i - 1] + a[i];
    for(register int i = 1;i <= n * 2;++ i)
        for(register int j = i;j <= n * 2;++ j)
            cost[i][j] = sum[j] - sum[i - 1];
    for(register int len = 1;len <= n;++ len)
    {
        for(register int i = 1;i + len - 1 <= n * 2;++ i)
        {
            int j = i + len - 1;
            if(i != j)
            f2[i][j] = 999999999;
            for(register int k = i;k < j;++ k)
                f1[i][j] = max(f1[i][j],f1[i][k] + f1[k + 1][j] + cost[i][j]),
                f2[i][j] = min(f2[i][j],f2[i][k] + f2[k + 1][j] + cost[i][j]);
        }
    }
    int M = 0;
    int MM = 0x7fffffff;
    for(register int i = 1;i <= n;++ i)
        M = max(M,f1[i][i + n - 1]),
        MM = min(MM,f2[i][i + n - 1]);
    cout << MM << endl << M << endl;
    return 0;
}