题解 CF803E 【Roma and Poker】

jzh817 · 2019-11-03 18:08:25 · 题解

这道题实际上就是一个记忆化搜索的模板题

题目要求输赢相差不超过k且在最后一回合是必须等于k，就可以用这做完终止条件

    if(x==n and abs(y)==k)return true;
    if(x==n or abs(y)>=k)return false;

然后，若当前回合输赢已经确定，就直接进入下一层递归；否则，枚举3种情况分别递归，只要有一种情况成立，就返回true

    if(s[x]=='W')return dfs(x+1,y+1);
    if(s[x]=='D')return dfs(x+1,y);
    if(s[x]=='L')return dfs(x+1,y-1);
    if(dfs(x+1,y+1))return s[x]='W',true;
    if(dfs(x+1,y))return s[x]='D',true;
    if(dfs(x+1,y-1))return s[x]='L',true;

然而，这样做肯定超时，于是开始记忆化搜索

用dp[x][y]表示在第x回合时赢的回合-输的回合数是y，当然，y有可能是负数

记忆化的过程也很简单，只要在递归函数中间加一个dp[x][y]=1就行了

上完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
    ll a=0,b=getchar(),c=1;
    while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
    while(isdigit(b))a=a*10+b-'0',b=getchar();
    return a*c;
}
int n,k,dp[1005][1005];
string s;
bool dfs(int x,int y){
    if(x==n and abs(y)==k)return true;
    if(x==n or abs(y)>=k)return false;
    if(dp[x][y])return false;
    dp[x][y]=1;
    if(s[x]=='W')return dfs(x+1,y+1);
    if(s[x]=='D')return dfs(x+1,y);
    if(s[x]=='L')return dfs(x+1,y-1);
    if(dfs(x+1,y+1))return s[x]='W',true;
    if(dfs(x+1,y))return s[x]='D',true;
    if(dfs(x+1,y-1))return s[x]='L',true;
}
int main(){
    n=read(),k=read();
    cin >> s;
    if(dfs(0,0))cout << s;
    else puts("NO");
    return 0;
}