[NOIP2010 普及组] 三国游戏

题目传送门

引

为了夯实基础

解法

考虑严谨证明一下最优策略
首先当小涵选了一个数后，一定会产生一个最优搭配和一个次优搭配，
明显最优搭配永远取不到，那么他就只能选次优搭配
还有一个选择是在选一个不相干的数，产生新的最优搭配，但是无济于事
所以最后一定是取最大的次优搭配

Code

#include 
#include 
#include 
#include 
#include 
#include 
using ll = long long ;
using namespace std;
const int N=2e5+7,M=1e6;
const ll mod=998244353,LLF=1e18;

int n;

int main(){
    scanf("%d",&n);
    vector > a(n+1);
    int ans=0;
    for(int i=1;i());
        ans=max(ans,a[i][1]);
    }
    printf("1\n%d",ans);
}
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

结

这算不算水博客呀