思路讲解
就是把D的连续改成了不一定连续
这个dp里存的是什么？
这个具体怎么想到这个dp里存的是什么要看这个视频，这个视频这方面讲的很清楚。
这个状态转移到底在干什么？其实是这样的，我们自然是枚举这个状态的最后一位是什么，这样我们才知道现在的状态是从哪里来的。
那么怎么状态转移？定义去掉最后一位的状态为pre，这个最后一位的数字肯定不会出现在dp[pre]之前，因为在dp[pre]之前，必然会截断一个成形的AA序列，无法正确形成这个状态。
故就是直接在dp[pre]这个位置后直接看有没有两位B，如果有，就是第二位B的位置，如果没有，就跳过。
1
2
3
4
5
6
7
| if(((i>>j)&1)==1){
ll pre=i-(1<<j);
ll res=upper_bound(pos[li[j]].begin(), pos[li[j]].end(), dp[pre])-pos[li[j]].begin()+1;
if(res>=pos[li[j]].size())
continue;
dp[i]=min(dp[i],pos[li[j]][res]);
}
|
AC代码
https://atcoder.jp/contests/abc381/submissions/61352128
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10,maxStatus=2e6+7;
ll n,T,A[N],kind;
int dp[maxStatus];
set<ll> diff;
ll li[25];
vector<int> pos[25];
inline void init(){
ll idx=0;
for(set<ll>::iterator it=diff.begin();it!=diff.end();it++){
li[idx++]=*it;
}
dp[0]=0;
for(int i=1;i<=1<<kind;++i){
dp[i]=9999999;
}
}
inline ll popcount(int x){
ll cnt=0;
while (x) {
x&=x-1;
++cnt;
}
return cnt;
}
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];
diff.insert(A[i]);
pos[A[i]].push_back(i);
}
kind=diff.size();
init();
for(int i=1;i<=(1<<kind)-1;++i){
for(int j=0;j<kind;++j){
if(((i>>j)&1)==1){
ll pre=i-(1<<j);
ll res=upper_bound(pos[li[j]].begin(), pos[li[j]].end(), dp[pre])-pos[li[j]].begin()+1;
if(res>=pos[li[j]].size())
continue;
dp[i]=min(dp[i],pos[li[j]][res]);
}
}
}
ll ans=0;
for(int i=(1<<kind)-1;i>0;--i){
if(dp[i]==9999999)
continue;
ans=max(ans,popcount(i));
}
cout<<ans*2<<endl;
return 0;
}
|
心路历程（WA，TLE，MLE……）
https://atcoder.jp/contests/abc381/submissions/61352084
问题出在这个<号，应该是≤
1
| for(int i=1;i<<=(1<<kind)-1;++i){
|