事实证明人还是不要太固执，我之前就是一定想要写一个搜索算法，但怎么写都TLE，即便我看了hint知道是dp，还是想写搜索，但最后一发dp AC了。怎么说呢，搜索的时间复杂度还是有点玄学，也可能是我学艺不精（bushi）。其实我感觉如果你知道这题是dp的话也不是说非常难写，毕竟我这个非常抗拒dp的写出来了嘛
思路讲解
我们先想一个朴素dp，一个牌可以换到n牌当且仅当他可以换到 n牌 或 之前可以换到n牌的牌（为简化，我们称之为A牌），那就把所有这些牌都遍历一下就知道能不能换到了。
当然这个朴素dp的时间复杂度就比较随缘，最坏情况可能有O（n**2），而且其实也不是很好写。
然后我们小小的优化一下（这种优化我感觉挺常见的），其实能不能换到就是看能不能换到A牌当中优先度最低的牌。
当然三个人对牌的优先度不同，我们用pair<char,int> lowq,lowk,lowj; 分别存一下A牌中在qkj中优先度最小的。
这是对他们的初始化
1
2
3
| lowq=make_pair('q',n);
lowk=make_pair('k',n);
lowj=make_pair('j',n);
|
我们以这段代码为例，这个牌成功换到了A牌中q优先度最小的，q不用更新，他的优先度肯定更高。
lowk以及lowj需要更新，这个 i 牌可能比他们的优先度更小。
1
2
3
4
5
6
7
8
| if(pq[i]>pq[lowq.second]) {
isReach[i]=true;
dp[i]=lowq;
if(pk[i]<pk[lowk.second])
lowk=make_pair('k',i);
if(pj[i]<pj[lowj.second])
lowj=make_pair('j',i);
}
|
最后答案输出就很简单了，跳着存入ans，玩过邻接表的都不会陌生
1
2
3
| for(int i=1;i<n;i=dp[i].second) {
ans.push_back(dp[i]);
}
|
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
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
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=static_cast<int>(2e5)+17;
int pq[N],pk[N],pj[N];
int T,n;
vector<pair<char,int> > ans;
bitset<N> isReach;
pair<char,int> dp[N],lowq,lowk,lowj;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
ans.clear(),isReach.reset();
for(int i=1;i<=n;++i) cin>>pq[i];
for(int i=1;i<=n;++i) cin>>pk[i];
for(int i=1;i<=n;++i) cin>>pj[i];
lowq=make_pair('q',n);
lowk=make_pair('k',n);
lowj=make_pair('j',n);
for(int i=n-1;i>=1;--i) {
if(pq[i]>pq[lowq.second]) {
isReach[i]=true;
dp[i]=lowq;
if(pk[i]<pk[lowk.second])
lowk=make_pair('k',i);
if(pj[i]<pj[lowj.second])
lowj=make_pair('j',i);
}
if(pk[i]>pk[lowk.second]) {
isReach[i]=true;
dp[i]=lowk;
if(pq[i]<pq[lowq.second])
lowq=make_pair('q',i);
if(pj[i]<pj[lowj.second])
lowj=make_pair('j',i);
}
if(pj[i]>pj[lowj.second]) {
isReach[i]=true;
dp[i]=lowj;
if(pk[i]<pk[lowk.second])
lowk=make_pair('k',i);
if(pq[i]<pq[lowq.second])
lowq=make_pair('q',i);
}
}
if(!isReach[1]) {
cout<<"NO"<<endl;
continue;
}
cout<<"YES"<<endl;
for(int i=1;i<n;i=dp[i].second) {
ans.push_back(dp[i]);
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();++i) {
cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
}
return 0;
}
|
心路历程（WA，TLE，MLE……）
一个暴搜dfs代码TLE
在第11个点TLE了，加了快读也不太行
19999个撑不住了
当然这个TLE之前肯定还出了点事，最重要的是把退出条件放在最前面，而且任何退出条件后进来的全部是多余的，ans需要pop一下。
1
2
3
4
| if(isFind) {
ans.pop_back();
return;
}
|
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
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=static_cast<int>(2e5)+17;
int pq[N],pk[N],pj[N];
int T,n;
bool isFind;
vector<pair<char,int> > ans;
bitset<N> vis;
void dfs(int x) {
if(isFind) {
ans.pop_back();
return;
}
if(x==n) {
isFind=true;
return;
}
if(vis[x])
return;
vis[x]=true;
for(int i=x+1;i<=n;++i) {
if(isFind)
return;
if(pq[i]<pq[x]) {
ans.emplace_back('q',i);
dfs(i);
if(!isFind)
ans.pop_back();
}
if(pk[i]<pk[x]) {
ans.emplace_back('k',i);
dfs(i);
if(!isFind)
ans.pop_back();
}
if(pj[i]<pj[x]) {
ans.emplace_back('j',i);
dfs(i);
if(!isFind)
ans.pop_back();
}
}
}
signed main()
{
cin>>T;
while (T--) {
cin>>n;
isFind=false,ans.clear(),vis.reset();
for(int i=1;i<=n;++i) {
cin>>pq[i];
}
for(int i=1;i<=n;++i) {
cin>>pk[i];
}
for(int i=1;i<=n;++i) {
cin>>pj[i];
}
dfs(1);
if(!isFind) {
cout<<"NO"<<endl;
continue;
}
cout<<"YES"<<endl;
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();++i) {
cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
}
return 0;
}
|