这应该是一道非常经典的区间类动态规划题了,题目描述可以参考P1880 [NOI1995]石子合并

首先,由于题目描述中石子是环装的,我们可以采用的方法是拆环为链或者做多次dp,前者占用的空间更大,但在这道题所规定的数据范围下显然无伤大雅。

然后得出dp方程dp(i,j) = max(dp(i,j) , dp(i,k)+dp(k,j)+cost(i,j))

但是在使用这个dp方程的过程中我们会发现,如果单纯的枚举i,j,k的话就会出现有些状态还没有被计算出来就用于下一层的状态转换了。(如i=1,j=6,k=3,显然dp(3,6)此时是没有被计算出来的)

那么我们这个时候可以采用枚举j-i来实现这个dp方程,参考程序如下。

也就是把这样的过程:

i k j . .

i k . j .

i k . . j

转化成了这样的过程

i k j . .

. i k j .

. . i k j

#include <bits/stdc++.h>
#define MAXN 101
#define f(a,b,c) for(int a=b;a<=c;++a)
using namespace std;

int n;
int sum[2*MAXN];
int dpmax[2*MAXN][2*MAXN];
int dpmin[2*MAXN][2*MAXN];
int maxans,minans;

int cost(int x,int y) {
    return sum[y] - sum[x-1];
    //由于数据不需要更改,直接用前缀和,实现O(1)查找
}

int main() {
    ios::sync_with_stdio(false);

    cin>>n;

    int temp;
    f(i,1,n) {
        cin>>temp;
        sum[i] = sum[i-1] + temp;
    }

    f(i,n+1,2*n) {
        sum[i] = sum[i-1] + sum[i-n] - sum[i-n-1];
    }
    //拆环为链

    f(p,1,n) {
         for(int i=1,j=i+p;(j<2*n) && (i<2*n);i++,j=i+p) {
            dpmin[i][j] = 9999999;
            f(k,i,j-1) {
                dpmax[i][j] = max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+cost(i,j));
                dpmin[i][j] = min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+cost(i,j));
            }
        }
    }

    minans = 999999999; 
    f(i,1,n) {  
        maxans = max(maxans,dpmax[i][i+n-1]);
        minans = min(minans,dpmin[i][i+n-1]);
    }  
    
    cout<<minans<<endl<<maxans;

    return 0;
}

当然,luogu题解区也有用四边形不等式来做的,也值得参考。

Last modification:December 3, 2018
博客维护不易,如果你觉得我的文章有用,请随意赞赏