第十八届同济大学程序设计竞赛暨高校网络友谊赛F-值钱的项链
题目链接
比较简单的一道线性DP，但是有些点非常恶心。
输入是先输入每个珠子的价值再输入每个珠子的颜色，所以必须先把珠子的价值全部存起来才能操作。而题目虽然保证了∑mn≤1×106，但却没规定m、n的具体值，所以得开动态数组来存。
设dp[i][j][k]表示：前i个珠子，且第i个珠子颜色为j，第1个珠子颜色为k时所能取得的最大价值。其中0≤j,k≤1，为0时表示蓝色，为1时表示红色。由于红色不能连续出现，那么状态转移方程就为
1
2
3
4
| dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][1][0]) + a0;
dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][1][1]) + a0;
dp[i][1][0] = dp[i - 1][0][0] + a1;
dp[i][1][1] = dp[i - 1][0][1] + a1;
|
其中，a0与a1分别表示i位置待选珠子中，蓝色珠与红色珠的最大价值。
但具体进行状态转移的时候要多加一些判断，保证当前待选的珠子中存在蓝/红色珠，否则不转移；由于存在这个不转移的状态，还需要保证用于转移的子状态是转移过的，否则也不转移。
最后取答案的时候，如果最后放的珠子是红色，那么第一颗珠子只能是蓝色，即
1
| res = max(dp[n][1][0], max(dp[n][0][0], dp[n][0][1]));
|
特别的，如果n的值为1，dp[n][1][1]又是可以取的，因为最后一颗珠子就是第一颗。
比赛的时候写这题出了不少问题，最严重的一个是在边输入颜色边操作的情况下，还一旦检测到答案不存在就退出操作了。这导致了数据输入混乱，全队查了几个小时才查出来。以后千万注意。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long dp[1000005][2][2];
vector<long long> val[1000005];
int main()
{
int _;
scanf("%d", &_);
while (_--)
{
int n, m, i, j;
long long a;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
dp[i][0][0] = dp[i][0][1] = dp[i][1][1] = dp[i][1][0] = -1;
val[i].clear();
val[i].push_back(0);
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
scanf("%lld", &a);
val[i].push_back(a);
}
}
long long a0 = -1, a1 = -1, num;
if (n > 0)
{
for (i = 1; i <= m; i++)
{
scanf("%lld", &num);
if (num == 0 && a0 < val[1][i])
a0 = val[1][i];
else if (num == 1 && a1 < val[1][i])
a1 = val[1][i];
}
}
dp[1][0][0] = a0;
dp[1][1][1] = a1;
bool flag = 0;
for (j = 2; j <= n; j++)
{
a0 = a1 = -1;
for (i = 1; i <= m; i++)
{
scanf("%lld", &num);
if (num == 0 && a0 < val[j][i])
a0 = val[j][i];
else if (num == 1 && a1 < val[j][i])
a1 = val[j][i];
}
if (max(dp[j - 1][0][0], dp[j - 1][1][0]) >= 0 && a0 >= 0)
dp[j][0][0] = max(dp[j - 1][0][0], dp[j - 1][1][0]) + a0;
if (max(dp[j - 1][0][1], dp[j - 1][1][1]) >= 0 && a0 >= 0)
dp[j][0][1] = max(dp[j - 1][0][1], dp[j - 1][1][1]) + a0;
if (dp[j - 1][0][0] >= 0 && a1 >= 0)
dp[j][1][0] = dp[j - 1][0][0] + a1;
if (dp[j - 1][0][1] >= 0 && a1 >= 0)
dp[j][1][1] = dp[j - 1][0][1] + a1;
}
long long res = max(dp[n][1][0], max(dp[n][0][0], dp[n][0][1]));
if (n == 1)
res = max(res, dp[n][1][1]);
printf("%lld\n", dp[n][0][0]);
}
return 0;
}
|