题目链接:
石子合并问题-直线版
狮子合并问题-圆形版
题意
相邻石子合并,每次合并的代价是两堆石子的重量之和,问最大代价和最小代价。
直线版就是石子的排列是一条直线,圆形版是成一个环装结构,可以合并头尾两端的石子堆。
思路
状态转移方程:
dp[i][j] = min/max(dp[i][j],dp[i][mid]+dp[mid+1][j]+sum[j]-sum[i-1]);
圆形版只要再在原先的末尾再接上一个相同的石子串即可。
AC代码
直线版
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
|
using namespace std; const int maxn = 1e3 + 7; int sum[maxn]; int dp[maxn][maxn]; int dp1[maxn][maxn]; void (void) { int n; std::ios::sync_with_stdio(false); while (cin >> n) { memset(dp, 0x3f, sizeof dp); memset(dp1, -1, sizeof dp1); memset(sum, 0, sizeof sum); for (int i = 1; i <= n; i++) { cin >> dp[i][i]; sum[i] = sum[i - 1] + dp[i][i]; dp[i][i] = dp1[i][i] = 0; } for (int size = 1; size < n; size++) { for (int i = 1; i + size <= n; i++) { int j = i + size; for (int mid = i; mid < j; mid++) { dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j] + sum[j] - sum[i - 1]); dp1[i][j] = max(dp1[i][j], dp1[i][mid] + dp1[mid + 1][j] + sum[j] - sum[i - 1]); } } } cout << dp[1][n] << ' ' << dp1[1][n] << endl; } } int main(void) { solve(); return 0; }
|
圆形版
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
|
using namespace std; const int maxn = 1e3 + 7; int sum[maxn]; int a[maxn]; int dp[maxn][maxn]; int dp1[maxn][maxn]; void (void) { int n; std::ios::sync_with_stdio(false); while (cin >> n) { memset(dp, 0x3f, sizeof dp); memset(dp1, -1, sizeof dp1); memset(sum, 0, sizeof sum); for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = sum[i - 1] + a[i]; dp[i][i] = dp1[i][i] = 0; } for (int i = 1; i <= n; i++) { sum[i + n] = sum[i + n - 1] + a[i]; dp[i + n][i + n] = dp1[i + n][i + n] = 0; } for (int size = 1; size < 2 * n; size++) { for (int i = 1; i + size <= 2 * n; i++) { int j = i + size; for (int mid = i; mid < j; mid++) { dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j] + sum[j] - sum[i - 1]); dp1[i][j] = max(dp1[i][j], dp1[i][mid] + dp1[mid + 1][j] + sum[j] - sum[i - 1]); } } } int ansmin = 0x3f3f3f; int ansmax = -1; for (int i = 1; i <= 2 * n; i++) { ansmin = min(dp[i][i + n - 1], ansmin); ansmax = max(dp1[i][i + n - 1], ansmax); } cout << ansmin << ' ' << ansmax << endl; } } int main(void) { solve(); return 0; }
|
近期评论