HRBUST 1819 石子合并问题--圆形版
2024-08-31 15:43:29
石子合并问题--圆形版
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HRBUST. Original ID: 1819
64-bit integer IO format: %lld Java class name: Main
在圆形操场上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。
每组第一行为n(n<=100),表示有n堆石子,。
二行为n个用空格隔开的整数,依次表示这n堆石子的石子数量ai(0<ai<=100)
Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input
3
1 2 3
Sample Output
9 11 解题:还是区间型dp,其实跟直线版的没什么区别,只要把原来的数组复制一份加到后面,求2n长度的。。。
#include <iostream>
#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
int maxS[maxn][maxn],minS[maxn][maxn],sum[maxn];
int main(){
int n;
while(~scanf("%d",&n)){
for(int i = ; i <= n; ++i){
scanf("%d",sum+i);
sum[i+n] = sum[i];
sum[i] += sum[i-];
}
for(int i = ; i <= n; ++i)
sum[i+n] += sum[i+n-];
int m = n<<,maxAns = -INF,minAns = INF;
for(int j = ; j <= n; ++j){
for(int i = ; i + j - <= m; ++i){
int t = i + j - ;
int tmp = sum[t] - sum[i-];
minS[i][t] = INF;
maxS[i][t] = -INF;
for(int k = i; k < t; ++k){
minS[i][t] = min(minS[i][t],minS[i][k]+minS[k+][t]+tmp);
maxS[i][t] = max(maxS[i][t],maxS[i][k]+maxS[k+][t]+tmp);
}
}
}
for(int i = ; i <= n; ++i){
minAns = min(minAns,minS[i][i+n-]);
maxAns = max(maxAns,maxS[i][i+n-]);
}
printf("%d %d\n",minAns,maxAns);
}
return ;
}
最新文章
- LBWE更新模式切换问题:缓存清理
- NSMutableAttributedString的使用
- gdb optimized out错误解决
- UITapGestureRecognizer 的用法
- 20141211—C#面向对象,封装
- Installing the Eclipse Plugin
- Eclipse ADT 插件安装慢的解决的方法
- 开机出现loading (hd0)/ntldr。。。
- Java注解--笔记
- JQ 实现轮播图(3D旋转图片轮播效果)
- Your local changes to the following files would be overwritten by merge:
- 「TJOI2015」概率论 解题报告
- 使用RabbitMQ实现延迟任务
- Mysql主从热备
- cannot convert from &#39;wchar_t *&#39; to &#39;char *&#39; 问题
- Spring Boot 2 实践记录之 使用 ConfigurationProperties 注解将配置属性匹配至配置类的属性
- Java线程:新特征-有返回值的线程《转》
- C#中关于系统用户信息持久化(接上文)
- DIV盒子介绍
- Java基础之基本数据类型的包装类型
热门文章
- 从client(content=&;quot;&;lt;p&;gt;&;lt;/p&;gt;&;quot;)中检測到有潜在危急的 Request.Form 值。
- mysql-高级语言语法
- HDU 3016 Man Down(线段树)
- 83.导入项目时,用npm install安装module
- Copying lists
- js封装each函数
- python中修改函数内部的变量会发生什么
- Chrome Foundation Services
- [JSOI2018]潜入行动 树形DP_复杂计数
- [HAOI2007]理想的正方形 单调队列 暴力