洛谷P9676 [ICPC 2022 Jinan R] Skills
P9676 [ICPC 2022 Jinan R] Skills
设计状态时，可以知道要用当前的压掉一维，\(dp_{i,j,0/1/2}\) 表示当前选第 \(0/1/2\) 种，\(i,j\) 表示其余两种的最后选择时间。
如果没有 \(0\) 的限制，我们可以很自然的看出 \(DP\) 方程。
首先，上次选的，这次也选。
// cur表示时间，now是cur&1
dp[now^1][i][j][0] = max(dp[now^1][i][j][0],dp[now][i][j][0]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][0]);
dp[now^1][i][j][1] = max(dp[now^1][i][j][1],dp[now][i][j][1]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][1]);
dp[now^1][i][j][2] = max(dp[now^1][i][j][2],dp[now][i][j][2]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][2]);
然后，上次选的，这次不选，一共 \(9\) 种。
dp[now^1][cur][j][1] = max(dp[now^1][cur][j][1],dp[now][i][j][0]-(j?cur-j+1:0)-1+val[cur+1][1]);
dp[now^1][cur][i][2] = max(dp[now^1][cur][i][2],dp[now][i][j][0]-(i?cur-i+1:0)-1+val[cur+1][2]);
dp[now^1][cur][j][0] = max(dp[now^1][cur][j][0],dp[now][i][j][1]-(j?cur-j+1:0)-1+val[cur+1][0]);
dp[now^1][i][cur][2] = max(dp[now^1][i][cur][2],dp[now][i][j][1]-(i?cur-i+1:0)-1+val[cur+1][2]);
dp[now^1][j][cur][0] = max(dp[now^1][j][cur][0],dp[now][i][j][2]-(j?cur-j+1:0)-1+val[cur+1][0]);
dp[now^1][i][cur][1] = max(dp[now^1][i][cur][1],dp[now][i][j][2]-(i?cur-i+1:0)-1+val[cur+1][1]);
再来一个性质，一个练习不可能掉成 \(0\)，否则不如一开始就给其他练习。
距离上一次不会超过 \(200\) 天。
做完了，时复 \(O(n\max{a_{i,j}})\)。
\(\Large \mathscr{Code}\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int T,n,m,val[N][4],dp[2][N][N][3],ans;
inline void DP(int cur,int i,int j){int now = cur&1;dp[now^1][i][j][0] = max(dp[now^1][i][j][0],dp[now][i][j][0]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][0]);dp[now^1][i][j][1] = max(dp[now^1][i][j][1],dp[now][i][j][1]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][1]);dp[now^1][i][j][2] = max(dp[now^1][i][j][2],dp[now][i][j][2]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][2]);dp[now^1][cur][j][1] = max(dp[now^1][cur][j][1],dp[now][i][j][0]-(j?cur-j+1:0)-1+val[cur+1][1]);dp[now^1][cur][i][2] = max(dp[now^1][cur][i][2],dp[now][i][j][0]-(i?cur-i+1:0)-1+val[cur+1][2]);dp[now^1][cur][j][0] = max(dp[now^1][cur][j][0],dp[now][i][j][1]-(j?cur-j+1:0)-1+val[cur+1][0]);dp[now^1][i][cur][2] = max(dp[now^1][i][cur][2],dp[now][i][j][1]-(i?cur-i+1:0)-1+val[cur+1][2]);dp[now^1][j][cur][0] = max(dp[now^1][j][cur][0],dp[now][i][j][2]-(j?cur-j+1:0)-1+val[cur+1][0]);dp[now^1][i][cur][1] = max(dp[now^1][i][cur][1],dp[now][i][j][2]-(i?cur-i+1:0)-1+val[cur+1][1]);
}
inline void work(){cin>>n;ans = 0;for(int i=1;i<=n;i++){cin>>val[i][0]>>val[i][1]>>val[i][2];}memset(dp,-0x3f,sizeof(dp));dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;for(int cur=0;cur<n;cur++){int now = cur&1;for(int i=max(0,cur-201);i<=cur;i++){for(int j=max(0,cur-201);j<=cur;j++){memset(dp[now^1][i][j],-0x3f,sizeof(dp[now^1][i][j]));}}for(int i=max(0,cur-201);i<=cur;i++){memset(dp[now^1][0][i],-0x3f,sizeof(dp[now^1][0][i]));}for(int i=max(0,cur-201);i<=cur;i++){memset(dp[now^1][i][0],-0x3f,sizeof(dp[now^1][i][0]));}memset(dp[now^1][0][0],-0x3f,sizeof(dp[now^1][0][0]));for(int i=max(0,cur-201);i<=cur;i++){for(int j=max(0,cur-201);j<=cur;j++){DP(cur,i,j);}}for(int i=max(0,cur-201);i<=cur;i++){DP(cur,0,i);}for(int i=max(0,cur-201);i<=cur;i++){DP(cur,i,0);}DP(cur,0,0);}for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){ans = max({ans,dp[n&1][i][j][0],dp[n&1][i][j][1],dp[n&1][i][j][2]});}}cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--) work();return 0;
}