题目链接：
石子合并问题-直线版
狮子合并问题-圆形版
题意
相邻石子合并，每次合并的代价是两堆石子的重量之和，问最大代价和最小代价。
直线版就是石子的排列是一条直线，圆形版是成一个环装结构，可以合并头尾两端的石子堆。
思路
状态转移方程:
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;
}
|
近期评论