石子合并问题--直线版 HRBUST - 1818
2019-08-16 07:59:05来源:博客园 阅读 ()
石子合并问题--直线版 HRBUST - 1818
t题目链接:https://vjudge.net/problem/HRBUST-1818
思路:一段已经合并的区间,分成两段区间,遍历所有能分开的区间。
代码有注释,基本就这样一个简单是思路。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <map> 7 #include <cmath> 8 #include <iomanip> 9 using namespace std; 10 11 typedef long long LL; 12 #define inf (1LL << 25) 13 #define rep(i,j,k) for(int i = (j); i <= (k); i++) 14 #define rep__(i,j,k) for(int i = (j); i < (k); i++) 15 #define per(i,j,k) for(int i = (j); i >= (k); i--) 16 #define per__(i,j,k) for(int i = (j); i > (k); i--) 17 18 19 const int N = 110; 20 int sum[N]; 21 int dpma[N][N]; 22 int dpmi[N][N]; 23 24 int main(){ 25 26 ios::sync_with_stdio(false); 27 cin.tie(0); 28 29 int n; 30 while(cin >> n){ 31 32 rep(i,1,n) rep(j,1,n){ 33 dpma[i][j] = 0; 34 dpmi[i][j] = inf; 35 } 36 37 int in; 38 rep(i,1,n){ 39 cin >> in; 40 sum[i] = sum[i - 1] + in; 41 } 42 43 rep(i,1,n){ 44 dpmi[i][i] = 0; //我这里直接从长度为2开始合并,然后遍历分区间 45 } 46 47 rep(l,2,n){ //合并的区间长度 48 rep(i,1,n - l + 1){ //开始位置 49 int e = i + l - 1; //结束为止 50 rep(o,i,e - 1){ //分段位置 51 int v = sum[e] - sum[i - 1]; 52 dpma[i][e] = max(dpma[i][e], dpma[i][o] + dpma[o + 1][e] + v); 53 dpmi[i][e] = min(dpmi[i][e], dpmi[i][o] + dpmi[o + 1][e] + v); 54 } 55 } 56 } 57 58 cout << dpmi[1][n] << ' ' << dpma[1][n] << endl; 59 } 60 61 getchar();getchar(); 62 63 return 0; 64 }
原文链接:https://www.cnblogs.com/SSummerZzz/p/11322141.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:hdu--1232 继续通畅工程
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
- 用C++实现:完美的代价 2020-04-15
- 用C++实现:FJ的字符串打印 2020-04-04
- 递归函数使用动态数组遇到的问题 2020-03-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash