题解：P9676 [ICPC2022 Jinan R] Skills

· · 题解

传送门

思路

动态规划，考虑怎么做。

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

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

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

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

自然，因为只有三项，对 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; // 完结撒花！！！
}