[NOI1995] 石子合并

题目描述

在一个圆形操场的四周摆放 \(N\) 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 \(2\) 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 \(N\) 堆石子合并成 \(1\) 堆的最小得分和最大得分。

输入格式

数据的第 \(1\) 行是正整数 \(N\)，表示有 \(N\) 堆石子。

第 \(2\) 行有 \(N\) 个整数，第 \(i\) 个整数 \(a_i\) 表示第 \(i\) 堆石子的个数。

输出格式

输出共 \(2\) 行，第 \(1\) 行为最小得分，第 \(2\) 行为最大得分。

样例 #1

样例输入 #1

4
4 5 9 4

样例输出 #1

43
54

提示

\(1\leq N\leq 100\)，\(0\leq a_i\leq 20\)。

实现

dp

代码

#include<bits/stdc++.h>
using namespace std;
const int N=300,MAXN=1e9;
int n,ans1,ans2,f1[N][N],f2[N][N],qzh[N],a[N];
/////////////ACACACACACACACACAC//////////////////
int d(int i,int j) {
    return qzh[j]-qzh[i-1];
}
/////////////ACACACACACACACACAC//////////////////
void pre() {
    for(int i=1; i<=2*n; i++) {
        qzh[i]=a[i]+qzh[i-1];
    }
}
/////////////ACACACACACACACACAC//////////////////
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        a[n+i]=a[i];
    }
    //memset(f2,0x3f,sizeof f2);
    pre();
    ans2=MAXN;
    for(int p=1; p<n; p++)
        for(int i=1,j=i+p; i<2*n&&j<2*n; i++,j++) {
            f2[i][j]=MAXN;
            for(int k=i; k<j; k++) {
                f1[i][j] = max( f1[i][j],f1[i][k] + f1[k+1][j] + d(i,j));
                f2[i][j] = min(f2[i][j],f2[i][k] + f2[k+1][j] + d(i,j));
                ans1=max(ans1,f1[i][j]);
            }
        }
    for(int i=1; i<=n; i++) {
        ans2=min(ans2,f2[i][i+n-1]);
    }
    cout<<ans2<<endl<<ans1<<endl;
    return 0;
}