DP 洛谷 P1880 [NOI1995]石子合并

题目描述

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

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

输入输出格式

输入格式：
 

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式：
 

输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例

输入样例#1： 复制

4

4 5 9 4

输出样例#1： 复制

43

54

题目分析：

由于是环状，我们需要把它转换为链状，那么就把存储石子的数组a[]空间开大一倍，从n+1~2*n存储的值等于1~n存储的值，那么只需要从1到n枚举链的开头即可，链尾则分别为n到2*n-1。这样计算和环状是等效的。
那么最优子结构是什么呢？如果有N堆，第一次操作肯定是从n-1个对中选取一对进行合并，第二次从n-2对中选取一对进行合并，以此类推……

求出a的前缀和s,s[0]设为0,s[i]表示a[1]+a[2]+...+a[i],这样的话a[i]+a[i+1]+...+a[j]就是s[j]-s[i-1].

f[i][j]表示从第i堆合并到第j堆的最小代价,则f[i][j]= min(f[i][k]+f[k+1][j]+s[j]-s[i-1])(i<=k<j),f[i][j]初始设置为

假设以7，6，5，7，100为例

输出fmin[i][j]

再次强调fmin[i][j]为第堆到第j堆最小代价

实现代码：

#include<bits/stdc++.h>
using namespace std;const int INF = 1 << 30;
int main()
{int n,a[1000],s[1000],fmin[205][205],fmax[205][205],i,j,k;memset(s,0,sizeof(s));memset(fmin,0,sizeof(fmin));memset(fmax,0,sizeof(fmax));cin>>n;for(i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}for(i=1;i<=2*n;i++)s[i]=s[i-1]+a[i];for(i=1;i<=n;i++){fmin[i][i]=0;fmax[i][i]=0;}for(int len=2;len<=n;len++)//归并的石子长度{for(i=1;i<=2*n-len+1;i++)//i为起点，j为终点{j=i+len-1;       //由于len,表示有len个石子进行归并,从i开始，由于只有相邻的石子才能合并,所以结束位置j=i+len-1fmin[i][j]=INF;    //初始值都置为无穷大for(k=i;k<=j-1;k++)  //中间断开位置，查找在[i,j]什么位置设置断点k，f[i][j]取最优值{fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+s[j]-s[i-1]);fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+s[j]-s[i-1]) ;}}}/* for(i=0;i<=2*n;i++)cout<<s[i]<<" ";cout<<endl;for(i=0;i<=2*n;i++){for(j=0;j<=2*n;j++)cout<<fmin[i][j]<<" ";cout<<endl;}cout<<endl;for(i=0;i<=2*n;i++){for(j=0;j<=2*n;j++)cout<<fmax[i][j]<<" ";cout<<endl;}*/int minn=INF,maxx=0;for (int i=1;i<=n;++i)//要把长度为n的都比大小{maxx=max(maxx,fmax[i][i+n-1]);minn=min(minn,fmin[i][i+n-1]);}cout<<minn<<endl<<maxx;return 0;
}