题解：AT_abc365_d [ABC365D] AtCoder Janken 3

Posted on Edited on In ,

AT_abc365_d [ABC365D]

前言

又是一道 dp 题……

翻译

先规定石头剪刀布的规则为：R 打败 S，S 打败 P，P 打败 R，出相同的字符视为平局。下简记三种出发为「手法」。

给出对方的 \(n\) 次出法的序列（一个长度为 \(n\) 字符串），要求你出一个对策，满足：

  • 你不会输任何一局（若平局不算为输给对方）。
  • 你出的相邻两个手法不能重复。

数据保证存在一种策略满足以上要求。

思路

引入

为什么不是贪心？

一种可能的思路是碰到对手一样的出发就隔一个赢一次，但是很幸运的没有过第 3 个样例。

各种分类后发现根本没有通用的方法，故采用 dp。

众所周知 dp 很多都是将暴力指数级算法优化成很多维的算法。但这道题只允许线性或 \(O(n\log n)\) 的算法通过，故确定复杂度且确定为线性 dp。

动态规划

若出了手法 \(s\) 出了下一个就不能 \(s\)，只能出不同于 \(s\) 的另外两个，不妨设另外两个为 \(s_1,s_2\)。

故转移为：\(dp(i,s)=dp(i+1,s_1)+dp(i+1,s_2)\)

其中 \(i\) 表示决策到了第 \(i\) 次，其他的如上文所述。

放代码：

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
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)

using namespace std;

typedef long long ll;
typedef double db;

const int N=2e5+23;

int n;
string s;
int mem[N][5],c[N];

/*
Paper 1
Sissor 2
Rock 3
*/

inline int dp(int d,int lst)
{
    int& ans=mem[d][lst];
    if(ans!=-1) return ans;
    if(d==n+1) return 0;
    int ans1=0,ans2=0;
    if(c[d]==1)
    {
        if(lst!=2) ans1=1+dp(d+1,2);
        if(lst!=1) ans2=dp(d+1,1);
    }
    if(c[d]==2)
    {
        if(lst!=3) ans1=1+dp(d+1,3);
        if(lst!=2) ans2=dp(d+1,2);
    }
    if(c[d]==3)
    {
        if(lst!=1) ans1=1+dp(d+1,1);
        if(lst!=3) ans2=dp(d+1,3);
    }
    return ans=max(ans1,ans2);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>n>>s;
    s=' '+s;
    rep(i,1,n)
    {
        if(s[i]=='P') c[i]=1;
        if(s[i]=='S') c[i]=2;
        if(s[i]=='R') c[i]=3;
    }
    memset(mem,-1,sizeof(mem));
    cout<<dp(1,0);
}

实现采用了思路比较清晰的记忆化搜索。

然后就愉快的 AC 了：https://www.luogu.com.cn/record/171653457

总结

类似于博弈、游戏等题目不能局限于贪心或一种方法，可以大胆开拓新的思路。

广告

安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。