文档章节

环形石子合并问题 - 经典DP问题

m2012
 m2012
发布于 2012/05/21 10:07
字数 514
阅读 2201
收藏 0

 

 ============================================================

 

又是一道超经典的题目。
对于线性的合并石子问题,dp模型类似于“加括号”那类型的dp题目,设 f(i, j)为 将第i项到第j项合并得到的最优解
关键是,这题目是环形的。环形结构,经常采用双倍长度线性化手段,也就是说,把环形结构看成是长度为环的两倍的线性结构来处理。
环的长度是N,所以题目相当于有一排石子1....N+N,然后就可以用线性的石子合并问题的方法做了。
有个要注意的地方,f(i, j) 总是与 f(N +i, N +j) 相等的,所以可以减少一些不必要的计算。

 

#include <cstdio>
#include <algorithm>
using namespace std;

int _sum[205];
int a[205];
int N;
int f[205][205];
int g[205][205];

int getSegmentSum(int i, int j) {
  return _sum[j] - _sum[i] + a[i];
}


int dp(int i, int j) {
  int & ans = f[i][j];
  if (ans != -1) return ans;

  if (i == j) return ans = 0;
  if (i + 1 == j) return ans = getSegmentSum(i , j);
  if (i <= N && j <= N) return ans = dp(N + i, N + j);

  ans = 2000000000;
  int s = getSegmentSum(i, j);
  for (int k = i; k < j; ++k) {
    ans = min(ans, dp(i, k) + dp(k + 1, j) + s);
  }
  return ans;

}


int dp2(int i, int j) {
  int & ans = g[i][j];
  if (ans != -1) return ans;

  if (i == j) return ans = 0;
  if (i + 1 == j) return ans = getSegmentSum(i , j);
  if (i <= N && j <= N) return ans = dp2(N + i, N + j);

  ans = -2000000000;
  int s = getSegmentSum(i, j);
  for (int k = i; k < j; ++k) {
    ans = max(ans, dp2(i, k) + dp2(k + 1, j) + s);
  }
  return ans;

}


void input() {
  int i, j;
  scanf("%d", &N);
  for (i = 1; i <= N; ++i) {
    scanf("%d", &(a[i]));
  }
  for (i = N + 1; i <= N + N; ++i) a[i] = a[i - N];
  _sum[1] = a[1];
  for (i = 2; i <= N + N; ++i) _sum[i] = a[i] + _sum[i - 1];

  for (i = 0; i < 205; ++i)
    for (j = 0; j < 205; ++j)
      f[i][j] = g[i][j] = -1;


}

int main() {
  input();
  int i, j;
  for (i = N + N; i >= 1; --i)
    for (j = i; j <= N + N; ++j)
    { dp(i, j); dp2(i, j); }

  int ans = 2000000000;
  for (i = 1; i <= N; ++i) {
    ans = min(ans, dp(i, i + N - 1));
  }

  int ans2 = -2000000000;
  for (i = 1; i <= N; ++i) {
    ans2 = max(ans2, dp2(i, i + N - 1));
  }
  printf("%d\n%d\n", ans, ans2);
  return 0;
}

© 著作权归作者所有

共有 人打赏支持
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
区间DP小结(附经典例题)

——这篇文章主要想总结下区间DP的经典题目,同时给自己复习巩固这方面知识点。 区间DP 一、定义 区间DP,顾名思义是在区间上DP,它的主要思想就是先在小区间进行DP得到最优解,然后再利用小...

my_sunshine26
2017/08/13
0
0
bzoj3598: [Scoi2014]方伯伯的商场之旅【数位dp】

Description 方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧,位置在 i 的人面前的第 j 堆的石子的数量,刚好是 i 写成 K 进制后的第...

cdsszjj
2018/02/05
0
0
HDU ~ 4745 ~ Two Rabbits (区间DP,环形序列的最长回文子序列)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/84989839 题意 有两只兔子和一个N块石头组成的环,他们在这个环跳,A顺时针跳,B逆时...

张松超
2018/12/13
0
0
动态规划:圆形石子合并问题

问题描述: 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。 规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 试设计一个算法,...

Iter_迟cH1
2016/09/01
30
0
【2017国庆雅礼集训划水记】 day1 四边形不等式

3道水提。。。 读入优化要考虑负数! 其他都很好。 据我估计,思维可能没有问题。有几个要注意的地方: - 打代码的时候要减少出错量,这个可以立即减少。注意一下就可以减少。 - 题做多的时候...

myjs999
2017/10/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

树形结构的数据库表Schema设计

程序设计过程中,我们常常用树形结构来表征某些数据的关联关系,如企业上下级部门、栏目结构、商品分类等等,通常而言,这些树状结构需要借助于数据库完成持久化。然而目前的各种基于关系的数...

太菜鸟
25分钟前
0
0
Pod在多可用区worker节点上的高可用部署

一、 需求分析 当前kubernetes集群中的worker节点可以支持添加多可用区中的ECS,这种部署方式的目的是可以让一个应用的多个pod(至少两个)能够分布在不同的可用区,起码不能分布在同一个可用...

迷你芊宝宝
34分钟前
0
0
使用maven命令上传jar包到仓库

mvn deploy:deploy-file -DgroupId=com.jz.tss.service -DartifactId=tss-service -Dversion=1.9.02-SNAPSHOT -Dfile=E:/Workspace/tss-service/build/oracle/TSS-Service/WEB-INF/lib/TSS-S......

GodIsCj
36分钟前
2
0
mysql 向下无限递归(不使用函数,单纯sql)

表结构和数据 CREATE TABLE table1(id int, name varchar(10), parent_id int); INSERT table1 VALUES (1, 'Home', 0), (2, 'About', 1), (3, 'Contact', 1), (4, 'Legal', 2), ......

一雨成东
36分钟前
0
0
面试官问:ZooKeeper 一致性协议 ZAB 原理

一致性协议有很多种,比如 Paxos,Raft,2PC,3PC等等,今天我们讲一种协议,ZAB 协议,该协议应该是所有一致性协议中生产环境中应用最多的了。为什么呢?因为他是为 Zookeeper 设计的分布式...

Java爬坑之路
39分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部