http://acm.nyist.net/JudgeOnline/problem.php?pid=737
資料很小,适合區間dp的入門
對于第[i, j]堆,無論你怎麼合并,無論你先選哪兩堆結合,當你把[i, j]合成一堆的那一步的時候,花費肯定就是sum[i....j]
可以用紙模拟下。
那麼我們設dp[i][j]表示把i...j堆合成一堆的時候的最小花費。
比如dp[1][1] = 0。dp[1][2] = a[1] + a[2];
那麼要求dp[i][j],則可以是dp[i][k] + dp[k + 1][j] + cost
注意dp的時候的順序,因為要求dp[1][n],則需要用到dp[1][k]和dp[k][n]
你需要考慮下怎麼for,才能使得子問題已經被算出,建議一開始用dfs + 記憶化做。
這裡dp的順序應該是先算出2個集合的,3個、4個、......
就是先算出dp[1][2], dp[2][3],這使得求dp[1][3]成為可能。
all dp[i][i] = 0
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 200 + 20;
int n;
int a[maxn];
int dp[maxn][maxn];
int sum[maxn];
int dfs(int be, int en) {
if (be > en) return 0;
if (be == en) {
return dp[be][en] = 0;
}
if (dp[be][en] != inf) return dp[be][en];
for (int k = be; k <= en; ++k) {
dp[be][k] = dfs(be, k);
dp[k + 1][en] = dfs(k + 1, en);
assert(dp[be][k] >= 0);
assert(dp[k + 1][en] >= 0);
dp[be][en] = min(dp[be][k] + dp[k + 1][en] + sum[en] - sum[be - 1], dp[be][en]);
// cout << dp[2][3] << endl;
}
return dp[be][en];
}
void work() {
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
memset(dp, 0, sizeof dp);
// cout << dfs(1, n) << endl;
// cout << dp[2][3] << endl;
for (int k = 1; k <= n - 1; ++k) {
for (int i = 1; i <= n - 1; ++i) {
int be = i;
int en = i + k;
if (en > n) break;
dp[be][en] = inf;
for (int h = be; h <= en - 1; ++h) {
dp[be][en] = min(dp[be][en], dp[be][h] + dp[h + 1][en] + sum[en] - sum[be - 1]);
}
}
}
printf("%d\n", dp[1][n]);
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d", &n) != EOF) work();
return 0;
}
View Code
平行四邊形優化,其實我還不是很懂。那個證明太難了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n;
const int maxn = 1e3 + 20;
int dp[maxn][maxn];
int s[maxn][maxn];
int sum[maxn];
void work() {
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
sum[i] = sum[i - 1] + x;
dp[i][i] = 0;
s[i][i] = i;
}
for (int dis = 1; dis <= n - 1; ++dis) {
for (int be = 1; be + dis <= n; ++be) {
int en = be + dis;
dp[be][en] = inf;
int t = s[be][en];
for (int k = s[be][en - 1]; k <= s[be + 1][en]; ++k) {
if (k + 1 > en) break;
if (dp[be][en] >= dp[be][k] + dp[k + 1][en] + sum[en] - sum[be - 1]) {
dp[be][en] = dp[be][k] + dp[k + 1][en] + sum[en] - sum[be - 1];
t = k;
}
}
s[be][en] = t;
}
}
cout << dp[1][n] << endl;
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d", &n) != EOF) work();
return 0;
}
View Code
簡單來說,就是設s[i][j]表示第i---j堆石子合并的時候,在第s[i][j]那裡合并,是最優的。