Znzryb's Blog
0%

Refact.ai Match 1 (Codeforces Round 985)——C. New Rating

Posted on Edited on

AC代码

dp0/1/2[0] i 之后的最高评分 ，代表其中 i 次比赛是在跳过的间隔之前/之中/之后。

其实没啥好多说的，就是题解2的思路，当然我的递推公式肯定比他复杂一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define  int long long

using namespace std;
const int N=static_cast<int>(3e5)+10;
int T,n;
int A[N],dp[N][5],ra[N];

struct record {
    int l,r,s;
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>T;
    while (T--) {
        cin>>n;
        for(int i=1;i<=n;++i) {
            cin>>A[i];
        }
        int curS=0;
        for(int i=1;i<=n;++i) {
            if(A[i]>curS) {
                curS+=1;
            }else if (A[i]<curS) {
                curS-=1;
            }
            ra[i]=curS;
        }
        if(curS==n) {       // 搞个特判
            cout<<curS-1<<endl;
            continue;
        }
        dp[1][0]=1;     // 前
        dp[1][1]=0;     // 中
        dp[1][2]=1;     // 后
        for(int i=2;i<=n;++i) {
            if(A[i]>dp[i-1][0])
                dp[i][0]=dp[i-1][0]+1;
            else if(A[i]<dp[i-1][0])
                dp[i][0]=dp[i-1][0]-1;
            else
                dp[i][0]=dp[i-1][0];
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]);    // 是继承空缺，还是继承连续，这是个问题
            int temp=0;
            if(A[i]>dp[i-1][1])
                temp=dp[i-1][1]+1;
            else if(A[i]<dp[i-1][1])
                temp=dp[i-1][1]-1;
            else
                temp=dp[i-1][1];
            int temp2;
            if(A[i]>dp[i-1][2])
                temp2=dp[i-1][2]+1;
            else if(A[i]<dp[i-1][2])
                temp2=dp[i-1][2]-1;
            else
                temp2=dp[i-1][2];
            dp[i][2]=max({dp[i][0],temp,temp2});
        }
        cout<<max(dp[n][1],dp[n][2])<<endl;
    }
    return 0;
}
// AC https://codeforces.com/contest/2029/submission/292353225

心路历程（WA，TLE，MLE……）

一次AC，dp是这样的