Znzryb's Blog
0%

ABC- 369 - D - Bonus EXP

Posted on Edited on

AC代码

总体思路其实就是对于暴力dp的优化，其实很多时候一些做法就是对暴力做法的优化，所以就算知道时间复杂度较高，也可以写一写试试，看看能不能优化。

思路就是C[i][isE]里面存的是从i点以是否是偶数进入，最优的v。

当然，把之前的全部遍历一遍肯定超时了，所以maxC[2]就登场了。

直接存的就是之前最优的奇数偶数情况，直接调用就行，当然记得更新。

AC

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,A[N];
ll C[N][3],maxC[2];     // C 即 cache
ll ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
    }
    for(int i=n;i>=1;--i) {
        ll isE=0;
        ll currMax[2];      // 搞一个local变量，避免互相影响在更新时
        currMax[0]=maxC[0];currMax[1]=maxC[1];
        C[i][isE]=A[i]+currMax[1-isE];
        maxC[isE]=max(maxC[isE],C[i][isE]);
        isE=1;
        C[i][isE]=A[i]*2+currMax[1-isE];
        maxC[isE]=max(maxC[isE],C[i][isE]);
    }
    C[1][1]-=2*A[1];    // 1是even的情况是不可能的，所以要减去1的双倍经验
    cout<<max(C[1][1],C[1][0])<<endl;
}

// AC https://atcoder.jp/contests/abc369/submissions/59513452

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