蒟蒻做noi系列的题,好慌……
题目描述
在一个圆形操场的四周摆放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
解析:
本蒟蒻第一次膜拜noi这么难的题,,,据说这题很多人用贪心做,导致直接爆了30。。。
本人虽然一上来就知道这绝对是道dp(绿题怎么可能是贪心~~~),但是是在orz了许多大佬的题解和董永建新出的某本书后才想出了正解。。。没办法,我反射弧长
下面我就来和大家分享一下这道题的解法。
这道题属于动态规划中的“区间dp”,顾名思义,区间dp是以区间长度作为阶段的,在本题中,所谓的“区间长度”其实可以形象地理解成一段区间合并的花费。
让我们先从最简单的情况入手。
假设现在这里有一条链(先不考虑环),有四个数,分别是1,2,3,4。
它们合并de情况有很多种,从最终状态考虑。分别是【(1),(2,3,4)】【(1,2),(3,4)】【(1,2,3),(4)】这三种;
毫无疑问,肯定是最后一种情况最省花费,研究它会发现,我们应该在(1,2,3)中再寻找最省花费的合并方法,而这些方法跟后边的合并显然没有关系,这也就符合无后效性原则。
接下来我们再把它抽象一点,假如我们现在得到了一条链。并且我们只需要去做最后的合并。
把这两部分合并起来,显然是左边的已有花费加上右边已有花费再加上他们的和(每次合并的花费)
以此类推到更多堆石子的情况。对于j到end之间的石子,去枚举“界限”,设在第k堆石子处分开,也就是第j到k堆合并,第k到end堆合并。
就有了状态转移方程:(f[i][j]表示i堆到j堆最小花费,g[i][j]表示从i堆到j堆最大花费)
f[j][end]=min(f[j][end],f[j][k]+f[k+1][end]+sum(j,end)); g[j][end]=max(g[j][end],g[j][k]+g[k+1][end]+sum(j,end));
还有一个比较难想的事情是如何把环转化成链,本蒟蒻的第一想法是去枚举端点,每次枚举一次,做一次dp,可是这样就是o(n4)的时间复杂度,即使对于n<=100来说也太大了。
于是董永建老人家为我们提供了一个更妙的思想。把这个环储存成一个更大的链。每次去枚举开头,自然就有了结尾。而且每种断开的方法都是这条链的字串(不是子序列!!!)。
最后打擂台取最大值即可。
还有一点,经常被人们忽略,就是调用的状态是否已经计算过。对于这道题,循环变量i表示在做第i-1次合并,所以合并是由小到大的,之前的状态是已经计算过的。
最后上ac代码
#include<iostream> #include<cstring> using namespace std; int n,a[301],prefix[200],end,f[205][205],g[205][205],maxn,minn=21370444;
//prefix前缀和,只需要进行线性的预处理,即可享受常数的求和方法(手动滑稽)(蒟蒻英语不好,上网百度的) int sum(int i,int j)//求第i堆到第j堆的和 { return prefix[j]-prefix[i-1]; } int main() { memset(f,20,sizeof(f));//初始化 cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i+n]=a[i];//构造更长的链 } for(int i=1;i<=n*2;i++) { prefix[i]=a[i]+prefix[i-1];//打前缀和 f[i][i]=0;//自己和自己合并不需要花费 g[i][i]=0; } for(int i=2;i<=n;i++) { for(int j=1;j<=2*n-i+1;j++)//j表示合并的左端点 { end=i+j-1;//end表示合并的右端点 for(int k=j;k<end;k++)//枚举断点 { f[j][end]=min(f[j][end],f[j][k]+f[k+1][end]+sum(j,end)); g[j][end]=max(g[j][end],g[j][k]+g[k+1][end]+sum(j,end)); } } } for(int i=1;i<=n;i++)//打擂台求最大最小 { maxn=max(g[i][i+n-1],maxn); minn=min(f[i][i+n-1],minn); } cout<<minn<<endl<<maxn<<endl; return 0;//终于结束了。。。 }
附上原题地址~~~:https://www.luogu.org/problemnew/show/p1880 ;
祝大家noip2019 rp++~~~
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603613.html