CodeForces 803E:Roma and Poker 记忆化搜索

本文主要是介绍CodeForces 803E:Roma and Poker 记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题目描述

给你一个n长度的字符串，‘W’和‘L’个数的差值在中途要小于k，且在最后的时候差值正好为k，‘D’表示平局，‘？’表示不确定。问是否存在这样的字符串，存在就输出，不存在就NO。

分析

有点类似于数位DP的写法？
记忆化搜索一下就可以了

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 10;
char str[N + 1];
map<int,int> M[N];
int n,m;bool dfs(int x,int y){if(x == (n + 1) && abs(y - (n + 1)) == m) return true;if(x == (n + 1) || abs(y - (n + 1)) >= m) return false;if(M[x][y]) return false;M[x][y] = 1;if(str[x] == 'W') return dfs(x + 1,y + 1);if(str[x] == 'L') return dfs(x + 1,y - 1);if(str[x] == 'D') return dfs(x + 1,y);if(dfs(x + 1,y + 1)) {str[x] = 'W';return true;}if(dfs(x + 1,y - 1)) {str[x] = 'L';return true;}if(dfs(x + 1,y)) {str[x] = 'D';return true;}
}int main(){scanf("%d%d",&n,&m);scanf("%s",str + 1);if(dfs(1,n + 1)) printf("%s",str + 1);else puts("NO");return 0;
}/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/