1、http://poj.org/problem?id=1738
2、题目大意：
有n堆石头排成一条直线 ，每堆石头的个数已知，现在要将这n堆石头合并成一堆，每次合并只能合并相邻的两堆石头，代价就是新合成石头堆的石头数，现在问将这n堆石头合并成一堆，最小代价是多少？
3、分析：
如果n的值较小，那么可以用dp[i][j]表示i-j堆合并成一堆的最小代价，那么dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j])
用区间DP做的代码，（本题不能这么做）
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 5005
#define INF 0x7ffffff
int a[N];
int dp[N][N];
int sum[N];
int main()
{int n;while(scanf("%d",&n)!=EOF){if(n==0)break;for(int i=1; i<=n; i++)for(int j=i; j<=n; j++)dp[i][j]=INF;sum[0]=0;for(int i=1; i<=n; i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];dp[i][i]=0;}if(n==1)printf("0\n");else{for(int d=2; d<=n; d++){for(int i=1; i<=n; i++){int s=i;int e=i+d-1;int add=sum[e]-sum[s-1];for(int k=s; k<=e; k++){dp[s][e]=min(dp[s][e],dp[s][k]+dp[k+1][e]+add);}}}printf("%d\n",dp[1][n]);}}return 0;
}
但是数据非常大，需要用GarsiaWachs算法，参考http://barty.ws/poj-1738-%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%E7%9A%84garsiawachs%E7%AE%97%E6%B3%95/
石子合并问题的普遍做法是动态规划。dp[i][j]表示从i合并到j这段石子所需的最小代价和。从小到大枚举区间就行了，此时复杂度为O(N^3)。又因为有四边形不等式优化，设f[i][j]为区间[i,j]的最优分界点，则有f[i][j-1]<=f[i][j]<=f[i+1][j]，复杂度就降为O(N^2)。
此时对于N=50000的复杂度来说依然不可接受。Knuth在TAOCP里有一个很神奇的算法，叫做GarsiaWachs。具体算法如下：
step 0：初始数组为num[1..n]，num[0] = num[n+1] = INF
step 1：每次找到一个最小的i使得num[i-1]<=num[i+1]，将num[i-1]和num[i]合并为temp
step 2：找到前面一个最大的j使得num[j]>temp，将temp放在j之后。
step 3：重复1,2，直到剩余的堆数为1。
因为每次step2之后，指向的位置只需要向前一个即可(前面其他的都不会受到此次更新的影响)，因此每次指针的移动并不多。也因此，一个理论复杂度其实有O(N^2)的算法能够轻松过掉这道题。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{int d;node* prev, *next;node(int _d){d = _d;prev = next = 0;} node() {}};
const int INF = 1000000000 + 1111111;
struct delink
{node* head, *tail;int size;void init(int n){size = n;if (!n) return;node* last;head = new node(INF);tail = head;last = head;for (int i = 0; i <= n; ++i){int x;if (i < n) scanf("%d", &x);else x = INF;tail = new node(x);tail->prev = last;last->next = tail;last = tail;}} int gao(){node* now = head->next, *tmp, *k;int tot = 0, t;while (size-- > 1){while (!now->prev || now->prev->d > now->next->d) now = now->next;t = now->prev->d + now->d;now->next->prev = now->prev->prev;now->prev->prev->next = now->next;k = now->prev->prev;now = new node(t);tot += t;while (k->d <= t) k = k->prev;now->next = k->next;now->prev = k;k->next->prev = now;k->next = now;now = now->prev;}return tot;}
} dq;
int main()
{int n;while (scanf("%d", &n), n){dq.init(n);printf("%d\n", dq.gao());}return 0;
}
还有一种方法也是正确的
参考http://blog.sina.com.cn/s/blog_803d08c00100xl3a.html
代码：
#include <iostream>
#include <cstdio>
#define Max 50000
using namespace std;
int stone[Max],n,t ;
int ret ;
void combine (int k)
{int tmp = stone[k] + stone[k-1] ;ret +=tmp ;for (int i=k ; i<t-1 ; i++ ){stone[i] = stone[i+1] ;}t-- ;int j ;for (j=k-1 ; j>0 && stone[j-1]<tmp ; j--){stone[j] = stone[j-1] ;}stone[j] = tmp ;while (j>=2 && stone[j]>=stone[j-2]){int d = t-j ;combine(j-1) ;j = t-d ;}
}int main()
{while (scanf("%d",&n),n){for (int i=0 ; i<n ; i++){scanf("%d",stone+i) ;}t=1,ret=0 ;for (int i=1 ; i<n ; i++){stone[t++] = stone[i] ;while (t>=3 && stone[t-3]<=stone[t-1]){combine(t-2) ;}}while (t>1) combine(t-1) ;printf("%d\n",ret) ;}return 0;
}