Skills - 2022 International Collegiate Programming Contest, Jinan Site, Problem J.

有3种技能，\(n(\le 10^3)\)天内每天可以对一个技能进行学习，第i天学习第j个技能可以为第j个技能增加\(a_{i,j}(\le 10^4)\)的熟练度。在第i天结束时，每个技能的熟练度会减去距离上次学习该技能的天数，但最多减到0。求n天后能得到的熟练度的和的最大值。

首先容易有一个显然的dp状态：\(f_{i,j,k}\) 表示三种技能上次被学习的天数，然后枚举接下来学哪个技能进行转移，这是 \(O(n^3)\) 的。

考虑减少状态数。注意到 \(a\) 的范围是比较小的，这意味着，一天能够获得的最大收益不会很高，那么也就是说长时间放置一个技能不去学习造成的亏损可能大过收益。具体的来说，假设技能 1 已经有 t 天没有学习，如果我放弃 s 天前的收益转而去学技能 1，那么我就会少亏 \(s(t-s)\)。所以一个技能一旦开始学习就不会放置超过 \(2\sqrt{a} +O(1)\) 天，状态数就减少到了 \(O(na)\)。

此题可以用斜率优化做到 \(O(n^2)\)。提示，若只有 2 种技能如何用 \(O(n)\) 解决？

2 种技能时，直接做状态是 \(O(n^2)\) 转移是 \(O(1)\)，我们平衡一下状态和转移。我们在状态中只记录当前的天数和今天学了哪个技能，\(f_{i,t=0/1}\) 表示第 \(i\) 天学了技能 \(t\)，并钦定接下来一定学习一段时间的 \(\neg t\)，这是因为如果接下来还学 \(t\)，就需要知道上一次学 \(\neg t\) 是什么时候来计算扣多少熟练度，这在我们的状态中并没有记录；而如果强制学 \(\neg t\)，则不需要知道这个信息。于是转移需要枚举 \(\neg t\) 要往后学到什么时候，变成了 \(O(n)\) 的转移。写出递推式后可以斜率优化到 \(O(1)\) 转移。

3 种技能时，我们延续上述思路。\(f_{i,j,t}\) 表示当前在第 \(i\) 天，一个技能上次学习在第 \(i\) 天，一个在第 \(j\) 天，还有一个在第 \(k\) 天但未放入状态，\(t\) 表示 \(i\)，\(j\) 分别是第几个技能。因为 \(k\) 未被放入状态，所以钦定接下来学习一段时间的技能 \(k\)。转移时分 \(k=0\)，\(0<k<j\) 和 \(j<k<i\) 的三种情况并注意 \(j=0\) 的处理，后两种维护凸包进行斜率优化即可做到 \(O(n^2)\)。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define endl '\n'
#define pL p<<1,l,mid
#define pR p<<1|1,mid+1,r
#define all(x) x.begin(),x.end()
void solve();
void init();
int main(){init();int t=1;cin>>t;while(t--)solve();
}void init(){#ifdef ONLINE_JUDGEcin.tie(nullptr)->ios::sync_with_stdio(false);cout.tie(nullptr);#endif}
const int N=1003,inf=1e9;
int s[N][3];
struct slope_opt{int x[N],y[N],h,t;void clear(){h=t=1;}void add(int x0,int y0){while(t-h>=2&&1ll*(y0-y[t-2])*(x0-x[t-1])<=1ll*(y0-y[t-1])*(x0-x[t-2]))--t;x[t]=x0;y[t]=y0;++t;}int query(int k){ // k decendwhile(t-h>=2&&1ll*k*(x[h+1]-x[h])<=(y[h+1]-y[h]))++h;if(t==h)return -inf;return y[h]-k*x[h];}
}A[6],B[6];int f[N][N][6];
int wa[]={5,3,4,1,2,0};
int wb[]={3,5,1,4,0,2};
int ts[]={0,0,1,1,2,2};
int fun(int x){return x*(x+1)/2;
}
void solve(){int n;cin>>n;for(int i=1;i<=n;i++){int a0,a1,a2;cin>>a0>>a1>>a2;s[i][0]=s[i-1][0]+a0;s[i][1]=s[i-1][1]+a1;s[i][2]=s[i-1][2]+a2;}int ans=0;for(int i=1;i<=n;i++)for(int t=0;t<6;t++){A[t].add(i-1,f[i-1][0][wa[t]]-s[i-1][ts[t]]-fun(i-2));int res=A[t].query(-i)+s[i][ts[t]]-fun(i);f[i][0][t]=max(s[i][ts[t]],res);if(i==n)ans=max(ans,f[i][0][t]);}for(int j=1;j<=n-1;j++){for(int t=0;t<6;t++){A[t].clear();B[t].clear();}for(int k=1;k<j;k++){for(int t=0;t<6;t++){B[t].add(k,fun(j-k)-fun(k-1)+f[j][k][wb[t]]);}}for(int i=j+1;i<=n;i++){for(int t=0;t<6;t++){if(i-j>1)A[t].add(i-1,fun(i-1-j)-s[i-1][ts[t]]-fun(i-2)+f[i-1][j][wa[t]]);int res=max(A[t].query(-i),B[t].query(-i)-s[j][ts[t]])-fun(i);f[i][j][t]=max(res,f[j][0][wb[t]]-s[j][ts[t]])+s[i][ts[t]]-fun(i-j);if(i==n)ans=max(ans,f[i][j][t]);}}}cout<<ans<<endl;
}