P1880 石子合并
2024-08-26 04:00:28
P1880 石子合并
题目描述
在一个园形操场的四周摆放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
分析
区间dp,不过是圆形的,把他们分成一个n*2的区间就好,然后进行区间dp ,对dp1不能全设成最大值,不然没法取min。
最后要在所有区间长度为n的区间中取出最大值与最小值。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = ;
int dp1[MAXN][MAXN],dp2[MAXN][MAXN],a[MAXN],sum[MAXN];
int n,ans1 = ,ans2 = ; int main()
{
scanf("%d",&n);
for (int i=; i<=n*; ++i)
for (int j=i+; j<=n*; ++j)
dp1[i][j] = 1e8; //最小值
memset(dp2,,sizeof(dp2)); //最大值
for (int i=; i<=n; ++i)
{
scanf("%d",&a[i]);
a[i+n] = a[i];
}
for (int i=; i<=n*; ++i)
sum[i] = sum[i-]+a[i];
for (int i=*n-; i>=; --i)//从倒数第二个开始枚举左端点
for (int j=i+; j<=*n; ++j)//枚举右端点
for (int k=i; k<=j-; ++k)//枚举中间点
dp1[i][j] = min(dp1[i][j],dp1[i][k]+dp1[k+][j]+sum[j]-sum[i-]),
dp2[i][j] = max(dp2[i][j],dp2[i][k]+dp2[k+][j]+sum[j]-sum[i-]);
for (int i=; i<=n; ++i)
{
ans1 = min(ans1,dp1[i][i+n-]);
ans2 = max(ans2,dp2[i][i+n-]);
}
printf("%d\n%d",ans1,ans2);
return ;
}
最新文章
- [LeetCode] Trapping Rain Water II 收集雨水之二
- PHP 中的Closure
- 如何获得中国所有的IP地址段
- CSS3选择器(一)之基本选择器
- js 传参报错 参数含有数字、字母组合的字符串SyntaxError: identifier starts immediately after numeric literal
- ASP.NET缓存OutputCache和Response.Cache之C#后台设置
- Relativelayout属性
- Windbg分析DMP文件
- Java 反射机制[Method反射]
- (大数据工程师学习路径)第二步 Vim编辑器----Vim文档编辑
- Webservice 中涉及的几个概念
- 网络通信 -->; epoll用法
- Docker(六):Docker 三剑客之 Docker Swarm
- Tomcat不停机部署项目
- Exp8 Web基础 20154320 李超
- gnuradio 使用eclipse 编辑器记录
- [Big Data - Suro] Netflix开源数据流管理器Suro
- Advances in Single Cell Genomics to Study Brain Cell Types | 会议概览
- HOJ 2091 Chess(三维简单DP)
- 洛谷2014选课(树型dp)