首页 > 代码库 > 【poj1738】 An old Stone Game
【poj1738】 An old Stone Game
http://poj.org/problem?id=1738 (题目链接)
题意
一排n堆石子，合并两堆石子的代价为两堆石子总数之和。问将所有石子合并为一堆所需要的最小代价。
Solution
本来想用刚学的四边形不等式练练手的，没想到n的范围竟然是50000，数组都开不下啊。。只好去看了下那个不明觉厉的GarsiaWachs。具体做法参见：http://blog.csdn.net/acdreamers/article/details/18043897。也真的是奇葩。。
代码
// poj1738#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<set>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=50010;int a[maxn],n,tot,ans;void unions(int x) { int tmp=a[x]+a[x-1]; ans+=tmp; for (int i=x;i<tot;i++) a[i]=a[i+1]; int j; for (j=x-1;a[j-1]<tmp && j>1;j--) a[j]=a[j-1]; a[j]=tmp;tot--; for (int d=tot-j;j>2 && a[j-2]<=a[j];d=tot-j) { unions(j-1); j=tot-d; }}int main() { while (scanf("%d",&n)!=EOF && n) { ans=tot=0; for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) { a[++tot]=a[i]; while (tot>2 && a[tot-2]<=a[tot]) unions(tot-1); } while (tot>1) unions(tot); printf("%d\n",ans); } return 0;}
【poj1738】 An old Stone Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。