考虑动态规划。

转移方程

首先读题可以明确出一个性质：当一种技能被选择后，其熟练度在此后不会降为 \( 0 \)，否则一定有更优的取法。 这样就只需要无需考虑熟练度为负的状态。定义 dp 方程 \( f_{i, j, k, h} \) 表示第 \( i \) 天选择了第 \( h \) 个技能，剩余两个技能的未练习天数为 \( j \) 和 \( k \) 时的熟练度。使用 \( j, k = 0 \) 的情况来表示时候未选择这个技能的情况。由此可以得出转移方程如下：

  • \( f_{i+1, nextj, nextk, h} \leftarrow \max(f_{i, j, k, h} + a_{i, h} - nextj - nextk) \) （选择当前技能的情况）
  • \( f_{i+1, nextk, 1, h + 1} \leftarrow \max(f_{i, j, k, h} + a_{i, h+1} - nextk - 1) \) （选择下一种技能的情况）
  • \( f_{i+1, 1, nextj, h+2} \leftarrow \max(f_{i, j, k, h} + a_{i, h+2} - nextj - 1) \) （选择下下种技能的情况）

其中 \( nextj = j + (j \neq 0) \)，\( nextk \) 同理。在处理 \( h \) 的时候可以进行对 \( 3 \) 取模来用 \( {0, 1, 2} \) 表示三种技能。

复杂度分析

这个 dp 的时间复杂度为 \( O(nm^2) \)，空间复杂度为 \( O(m^2) \)（显然可以用滚动数组滚掉第一维），其中 \( m \) 为未联系天数的值域。注意到在选择一个值 \( x \) 后，降到 \( 0 \) 的天数不超过 \( \sqrt{2x} \)，因此 \( m \leq \sqrt{\max a_{i, j}} \)。令 \( a \) 值域为 \( W \)，则 dp 时间复杂度为 \( O(nW) \)，空间复杂度 \( O(W) \)，可以通过此题。注意多测清空，以及滚动数组也要清空，因为这道题不能保证 \( f_{i, j, k, h} > f_{i - 2, j, k, h} \)。全 \( 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
int n, a[N][3];
int f[M][M][3], g[M][M][3];
int mx, p;
void cpy() {
	for(int i = 0; i <= mx; i++) for(int j = 0; j <= mx; j++) for(int k = 0; k < 3; k++) g[i][j][k] = f[i][j][k], f[i][j][k] = 0;
	return void(0);
}
void solve() {
	cin >> n;
	p = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			cin >> a[i][j];
			p = max(p, a[i][j]);
		}
	}
	mx = 2 * sqrt(p + 1);
	for(int i = 0; i <= mx; i++) for(int j = 0; j <= mx; j++) for(int k = 0; k < 3; k++) f[i][j][k] = g[i][j][k] = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= min(mx, i); j++) for(int k = 0; k <= min(mx, i); k++) for(int h = 0; h < 3; h++) {
			int nj = j + (j != 0), nk = k + (k != 0);
			f[nj][nk][h] = max(g[j][k][h] + a[i][h] - nj - nk, f[nj][nk][h]);
			f[nk][1][(h + 1) % 3] = max(g[j][k][h] + a[i][(h + 1) % 3] - nk - 1, f[nk][1][(h + 1) % 3]);
			f[1][nj][(h + 2) % 3] = max(g[j][k][h] + a[i][(h + 2) % 3] - nj - 1, f[1][nj][(h + 2) % 3]);
		}
        cpy();
	}
	int res = 0;
	for(int i = 0; i <= mx; i++) for(int j = 0; j <= mx; j++) for(int k = 0; k < 3; k++) res = max(res, g[i][j][k]);
	cout << res << '\n';
	return void(0);
}