[NOI1995]石子合并

· · 题解

题目解析：

　　第一次做这种题型的大佬们应该不会把它当成贪心来做吧？？？反正小蒟蒻我是做错了啦！！！

后面有分析了几个手推数据，发现！！！ 这是一题动规，还是一题区间动规！！！

让我们先看看样例： 这是最小值的求法，看起来好像和贪心很像勒！！！但其实只是样例数据给出的假象罢了！！！

　 　很多的大佬和蒟蒻做题时用了贪心结果只有30分！！！

　 　首先如何解决上图环的问题呢？？？ 　 当然很简单啦，我们把它存成一条链：即把T存成2*T

　 　如：2 3 4 6 5 4 2 3 4 6 5 4 这样每次枚举i到i+N-1就可以了是吧是不是很简单啊(^▽^ ) (i<=N)

　 　上文我们说到这是一题动规，那么我们来分析一下：

　　1.根据题意可知每次都是两堆石子合并成一堆，并且这两堆石子是相邻的！！

　　那么这两堆石子又是由另外的石子合并的，那么我们可以认为i到j堆石子是由F[i][k]和F[k+1][j]合成的。那么F[i][k]也是根据上面的规则求得到！！！

　　 2.那么合成的分数如何表示的呢？？？( -'`-)

　 　已知每个点的分数都是确定的，那么无论前面的数据如何合并的分数一定是由前面sum[j]-sum[i-1]的值，sum[i]=sum[i-1]+T[i];， 　　 因此得到F[i][j]=max(F[i][k]+[k+1][j]+sum[j]-sum[i-1],F[i][j]); 　　 　 　至此这题大水题已经解决了剩下的只是要考虑合并几次的问题而已

　　 因为第一次至少两堆合并，那么就有了L (L=2；L<=N;++L)j=i+L-1;

　　 最后就是求一下答案枚举一遍就行了！！

　　 下面正解代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=0xfffff,MINN=0;
inline int read()//快读
{
    int x=0,w=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-',ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    }
    return w?-x:x;
}
int T[210],F1[210][210],F2[210][210],sum[210];//T为输入的石子堆，F1为第一问的答案求解，F2为第二问的答案求解，sum为求前ｉ堆石子的合总值
int main(void)
{
    int N=read();
    for(int i=1; i<=N; ++i) T[i]=read(),T[i+N]=T[i];／／变环为链
    for(int i=1; i<=2*N; ++i) sum[i]=sum[i-1]+T[i],F1[i][i]=0,F2[i][i]=0;//注意要把Ｆ［ｉ］［ｉ］＝０
    for(int L=2; L<=N; ++L)
    {
        for(int i=1; i<=2*N-L+1; ++i)
        {
            int j=i+L-1;
            F1[i][j]=MAXN,F2[i][j]=MINN;//初始化
            for(int k=i; k<j; ++k)
            {

                F1[i][j]=min(F1[i][k]+F1[k+1][j],F1[i][j]);//寻找最小值
                F2[i][j]=max(F2[i][k]+F2[k+1][j],F2[i][j]);//寻找最大值
            }
            F1[i][j]+=(sum[j]-sum[i-1]);//加上此次合并值
            F2[i][j]+=(sum[j]-sum[i-1]);
        }
    }
    int ANS1=MAXN,ANS2=MINN;
    for(int i=1; i<=N; ++i)
    {
        ANS1=min(ANS1,F1[i][i+N-1]);//求解答案１
        ANS2=max(ANS2,F2[i][i+N-1]);//求解答案２
    }
    printf("%d\n%d",ANS1,ANS2);//输出
    return 0;
}