本文共 3807 字，大约阅读时间需要 12 分钟。
1、
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#include using namespace std;#define N 5005#define INF 0x7ffffffint 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算法，参考
石子合并问题的普遍做法是动态规划。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#include #include 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;}
还有一种方法也是正确的
参考
代码：
#include#include #define Max 50000using 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 0 && stone[j-1] =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 =3 && stone[t-3]<=stone[t-1]) { combine(t-2) ; } } while (t>1) combine(t-1) ; printf("%d\n",ret) ; } return 0;}
转载地址：http://rgddi.baihongyu.com/