Solution

设 dp_{i,0/1/2} 表示到第 i 次比赛时还没进行过跳过操作，正在进行跳过操作，已经进行过跳过操作的最高 rating。设 f(x,y) 为题目中的 rating 变化函数。枚举 a_i 可能的状态，转移为：dp_{i,0}=f(dp_{i-1,0},a_i),dp_{i,1}=\max(dp_{i-1,0},dp_{i-1,1}),dp_{i,2}=\max(f(dp_{i-1,1},a_i),f(dp_{i-1,2},a_i))。初始化 dp_{0,1}=dp_{0,2}=-\infty，答案为 \max(dp_{n,1},dp_{n,2})。

Code

#include<bits/stdc++.h>
inline int calc(int x,int y){
    return x+(x<y?1:x==y?0:-1);
}
int dp[300005][3];
int a[300005];
int T,n;
int main(){
    dp[0][1]=dp[0][2]=0xc0c0c0c0;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;scanf("%d",&a[i++]));
        for(int i=1;i<=n;++i){
            dp[i][0]=calc(dp[i-1][0],a[i]);
            dp[i][1]=std::max(dp[i-1][0],dp[i-1][1]);
            dp[i][2]=std::max(calc(dp[i-1][1],a[i]),calc(dp[i-1][2],a[i]));
        }
        printf("%d\n",std::max(dp[n][1],dp[n][2]));
    }
    return 0;
}