洛谷P1880 [NOI1995]石子合并 纪中21日c组T4 2119. 【2016-12-30普及组模拟】环状石子归并
洛谷P1880 石子合并 纪中2119. 环状石子归并
题目描述1
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入格式
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
4
4 5 9 4
43
54
(File IO): input:stone.in output:stone.out
题目描述2
在一个环状跑道上摆放着N堆石子，现在要将所有的石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。问最少的总得分是多少？
输入
第一行为石子堆数N。
从第2行到第N + 1行，每行一个正整数。第i个数表示第i堆石子的石子数。
输出
在第一行输出一个整数，表示最少的总得分。
样例输入
4
4
5
9
4
样例输出
43
数据范围限制
在40%的数据中，1 ≤ N ≤ 100
在60%的数据中，1 ≤ N ≤ 200
在100%的数据中，1 ≤ N ≤ 2000
保证输入数据中每堆石子的石子数不超过10000
Solution
此题为区间DP+四边形不等式
这是我第一次见到区间DP
洛谷上既要求最大值，也要求最小值，（多写几句话的事~）但是数据范围最大只有100
jzoj上就恶心了，虽然只要求最小值，但是数据范围最大为2000！
Algorithm1
标准的区间DP
由于这是环形的，所以要把整个跑道复制一遍
可以在输入的同时操作
（约定：s[i]表示第i（0~n-1）堆石子的数量）
for(int i=;i<n;i++) cin>>s[i],s[i+n]=s[i];
做DP前要先弄清楚“阶段”，“状态”，“决策”；
由于首先要合并两堆，再在两堆的基础上合并三堆，再在三堆的基础上合并四堆……以此类推。
并且，每次要选相邻的两堆合并（这就是为什么不能像“合并果子那样使用贪心”）
所以，每一个阶段就是合并去=的区间长度 len
这个len在循环的最外层，从2至n（最少合并2堆）
其次是状态
状态即为最初的第l堆石子和第r堆石子被合并，
同时l~r这段区间的长度为阶段——len。
所以我们要枚举的状态就是左端点
范围：左极限为0，右极限为右端点<n
最内层是决策
顾名思义：
就是决定当前应该选哪两堆来合并
对于目前长度为len的区间[l,r)
可以选出一个中间点k∈[l,r)
表示先合并了[l,k]，再合并[k+1,r)
所以决策就是中间点k
同时还要计算合并这两堆石子所需要的体力（即为两堆石子的石子数量之和）
可以使用前缀和计算
Code1
洛谷Code
#include<iostream>//不想OI一场空，千万别用万能头
#include<algorithm>//快排sort()
#include<cstdio>//能不用cin就不用
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define IL inline
using namespace std; int s[],n,minn=0x3f3f3f3f,maxn;
int dpmin[][],dpmax[][];
int sum[];
int main()
{
cin>>n;
memset(dpmin,0x3f,sizeof(dpmin));
for(int i=;i<n;i++) cin>>s[i],s[i+n]=s[i];
for(int i=;i<*n;i++)
dpmin[i][i]=;
sum[]=s[];
for(int i=;i<*n;i++) sum[i]=sum[i-]+s[i];
for(int len=;len<=n;len++)
{
for(int l=;l+len-<*n;l++)
{
for(int k=l;k<l+len-;k++)
dpmin[l][l+len-]=min(dpmin[l][l+len-],dpmin[l][k]+dpmin[k+][l+len-]),
dpmax[l][l+len-]=max(dpmax[l][l+len-],dpmax[l][k]+dpmax[k+][l+len-]);
dpmin[l][l+len-]+=sum[l+len-]-sum[l-];
dpmax[l][l+len-]+=sum[l+len-]-sum[l-];
}
}
for(int i=;i<n;i++)
minn=min(minn,dpmin[i][i+n-]),maxn=max(maxn,dpmax[i][i+n-]);
cout<<minn<<endl<<maxn;
return ;
}
纪中Code1（70分）
#include<iostream>//不想OI一场空，千万别用万能头
#include<algorithm>//快排sort()
#include<cstdio>//能不用cin就不用
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define IL inline
using namespace std; int s[],n,minn=0x3f3f3f3f;
int f[][];
int sum[];
IL int read()
{
int res=;
char ch=getchar();
while(ch<''||ch>'')
ch=getchar();
while(ch>=''&&ch<='')
res=(res<<)+(res<<)+(ch^),ch=getchar();
return res;
} int main()
{
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
n=read();
memset(f,0x3f,sizeof(f));
for(int i=;i<=n;i++) s[i]=read(),s[i+n]=s[i];
for(int i=;i<=*n;i++)
f[i][i]=,sum[i]=sum[i-]+s[i];
for(int len=;len<=n;len++)
{
for(int l=;l+len-<=*n;l++)
{
for(int k=l;k<l+len-;k++)
f[l][l+len-]=min(f[l][l+len-],f[l][k]+f[k+][l+len-]);
f[l][l+len-]+=sum[l+len-]-sum[l-];
}
}
for(int i=;i<=n;i++)
minn=min(minn,f[i][i+n-]);
cout<<minn;
return ;
}
纪中Code1
为什么折叠？
纪中此题的范围是2000，要用到四边形不等式优化成n2才能过……毒瘤呀
Attention1
所有数组都要开两倍大——这是环状变链状。
Algorithm2
四边形不等式
对于一个函数f(i,j)，有四个值a<=b<c<=d
使得f(a,b)+f(c,d)<f(a,c)+f(b,d)
那么这个函数满足四边形不等式
可以放到决策k时使用
至于证明嘛……打表证吧
Impression
2019-08-22 11:51:55
与此同时……
哪个人知道我们听不懂今天的讲课会都回来，故意放了比赛？？？
最新文章
- 小学徒成长系列—StringBuilder & StringBuffer关键源码解析
- ClientScript.RegisterStartupScript 不起作用
- Java的数据类型
- JAVA04类与对象之课后问题解决
- android: SQLite升级数据库
- 经典的单例模式c3p0来控制数据库连接池
- Spring MVC 完整示例
- elk工作原理
- UIColor，CGColor，CIColor三者间的区别和联系
- CSS 圣杯布局升级版---多个固定宽度一个自适应宽度
- POJ 3590 The shuffle Problem
- OpenCV+OpenCL stereo match 代码
- python requests库爬取网页小实例：ip地址查询
- 背水一战 Windows 10 (117) - 后台任务: 后台下载任务
- Hadoop、Spark 集群环境搭建问题汇总
- MyBatis学习笔记(二)——使用MyBatis对表执行CRUD操作
- Servlet拓展
- WPF 应用程序资源、内容和数据文件
- 文本检查点web_reg_find和web_find两个函数的区别
- c++ what happens when a constructor throws an exception and leaves the object in an inconsistent state?