自动搬运

查看原文

来自洛谷，原作者为

	fishing_cat にゃんぱすー ！

搬运于2025-08-24 22:50:38，当前版本为作者最后更新于2024-11-08 09:10:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传送门

思路

动态规划，考虑怎么做。

先想一个最普通的转移，然后看是否可以优化。设 $f_{i, j, k, h}$，每一维分别表示现在是第几天，练习的编号下一项有多久没练了，编号下下项有多久没练了，练的是哪个。

哎？这不看起来没有哪一维可以缩掉吗？确实，那先把最基础的转移写出来看看。

首先考虑，在一项技能从没有被练习时，是不会有熟练度负增长的，自然也就不存在所谓的有多久没练了。所以在转移时，将第二，三维下标为 $0$ 定义为没练习过，方便转移。由此，可以发现对下一次状态的二，三维的计算应该是 $j_{next} = j_{now} + (j_{now} \ne 0)$，$k$ 同理。

对于每一次转移，有三种操作。

• 继续练上一次练的

$$f_{i, j_{next}, k_{next}, h} = \max(f_{i-1, j_{now}, k_{now}, h} + a_{i,h} - j_{next} - k_{next}) $$

• 换练编号下一项

$$f_{i, k_{next}, 1, h+1} = \max(f_{i-1, j_{now}, k_{now}, h} + a_{i,h+1} - 1 - k_{next}) $$

• 换练编号下下项

$$f_{i, 1, j_{next}, h+2} = \max(f_{i-1, j_{now}, k_{now}, h} + a_{i,h+2} - j_{next} - 1) $$

自然，因为只有三项，对 $h$ 做加法，溢出三的要绕回来。

可以想一下，没练的负增长是指数级的，所以第二，三维实际上限不会太大，超出上限后是一定不优的。现在考虑怎样把这个上限求出来。设一次练习加的熟练度是 $x$，假设 $y$ 天不练后将变得不优，可以列出 $x - \frac{y(y-1)}{2} \le 0$，大体估算求出 $y \ge 2\sqrt{x}$ 时是不优的。所以上限就是 $2\cdot \sqrt{\max(a_{i,j})}$。这样就将二，三维优化下来了。

现在的时间复杂度就是 $O(n\cdot \max(a_{i,j}))$。好耶，可以过了！！！等一等，你要不要算一下空间。最后一步，滚动数组，把第一维滚掉。

code

link

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
/*快读省了*/
ll t, n, a[1100][4], ans = -inf;
ll f[3]/*  */[214]/*        */[214]/*   */[4];
// 第几天 下一项没练天数 下下项没练天数 练了哪个
//         0->未被练习过  0->未被练习过
il ll get(ll x) {
	if (x > 3) { return x - 3;}
    return x;
}

int main() {
	read(t);
	while (t--) { 
		read(n);
		ans = -1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 3; j++) {
				read(a[i][j]);
				ans = max(ans, a[i][j]);
			}
		}	
		int MAX = 2*sqrt(ans);// 上限
		// init
		for (int now = 0; now <= 1; now++)
			for (int j = 0; j <= MAX; j++) 
				for (int k = 0; k <= MAX; k++) 
					for (int h = 1; h <= 3; h++) 
						f[now][j][k][h] = 0;		
		ll now = 1;
		for (int i = 1; i <= n; i++) {
			ll last = now ^ 1;
			// init
			for (int j = 0; j <= MAX; j++) 
				for (int k = 0; k <= MAX; k++) 
					for (int h = 1; h <= 3; h++) 
						f[now][j][k][h] = 0;			
			for (int j = 0; j <= min(MAX, i); j++) 
				for (int k = 0; k <= min(MAX, i); k++) 
					for (int h = 1; h <= 3; h++) {
						// strat 转移
						ll u = j + (j!=0), v = k + (k!=0), LAST = f[last][j][k][h];
						f[now][u][v][h] = max(f[now][u][v][h], LAST + a[i][h] - u - v);
						/*继续原来的*/
						f[now][v][1][get(h+1)] = max(f[now][v][1][get(h+1)], LAST + a[i][get(h+1)] - 1 - v);
						/*转下一项*/
						f[now][1][u][get(h+2)] = max(f[now][1][u][get(h+2)], LAST + a[i][get(h+2)] - u - 1);
						/*转下下项*/
					}
			now ^= 1;
		}
		ans = -1;
		for (int j = 0; j <= MAX; j++) 
			for (int k = 0; k <= MAX; k++) 
				for (int h = 1; h <= 3; h++) {
					ans = max(ans, f[now ^ 1][j][k][h]);
				}
		printf("%lld\n", ans);
	}
	return 0; // 完结撒花！！！
}