Educational Codeforces Round 20 E. Roma and Poker

http://codeforces.com/contest/803/problem/E

N,K <= 1000

포커게임을 하는데 주인공 기준에서 경기결과 는 D(Draw), W(Win), L(Lose) 세가지이며

전날 N판에 대한 경기 결과 목록이 있는데

중간 중간 몇개를 까먹어서 ? 로 되어있다. 이 때 주어진 조건을 만족하면서 어제 까먹은 경기 결과를 예측하는 것인데

조건이 뭐냐면 지금까지 경기한 것을 봤을 때 내가 진횟수와 이긴횟수가 K번 이상 차이가 나는 순간 경기를 그만둔다는 사실을

만족하도록 경기결과를 정해주는 것이다. 물론 애초에 불가능한 경우도 있으며, 답이 여러개인 경우도있다.

불가능한 경우는 NO를 출력, 여러개인 경우는 아무거나 하나 출력.

그렇기 때문에 마지막 판을 제외하고는 진횟수가 이긴횟수가 K번 이상으로 차이나지않도록 L,D,W 중에 잘 정해줘야 하며

마지막은 무조건 진 횟수가 이긴횟수보다 딱 K번 많거나 딱 K번 적거나 둘중 하나여야만 한다는 것이다.

이것은 DP로 풀 수 있다. 

dp(pos, score) : pos 번째 판의 경기결과를 정해주어야 하며

현재 점수가 score('이긴횟수-진횟수'를 양수가 되도록 2K만큼 올려준거) 일때 가능한지 여부

그렇다면 현재 보고있는 결과가 이미 W,D,L 로 정해져 있다면 그냥 지나가면되고 ?일때만 세가지 경우를 다 봐준다.

중간에 가능한 경우가 하나라도 발견되면 다 빠져나온다. ? 판에서 W,D,L 중에 하나를 정해주면서 동시에 실제 답을 조립해간다.

기저는 마지막판까지 봤을 때 score 가 0 이거나 2K 인지를 반환

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int dp[1003][1003];
int N,K;
string str;
char ans[1003];
int go(int pos, int score){
    if(pos == str.size()) return score == 0 || score == 2*K;
    int& cache = dp[pos][score];
    if(cache != -1) return cache;
 
    int ret = 0;
    if(score <= 0 || score >= 2*K) return cache = 0;
    if(str[pos] == 'W') return ans[pos] = 'W', cache = go(pos+1, score+1);
    else if(str[pos] == 'D') return ans[pos] = 'D', cache = go(pos+1, score);
    else if(str[pos] == 'L') return ans[pos] = 'L', cache = go(pos+1, score-1);
    
    ans[pos] = 'L';
    if(go(pos+1, score-1)) return 1;
    
    ans[pos] = 'D';
    if(go(pos+1, score)) return 1;
 
    ans[pos] = 'W';
    if(go(pos+1, score+1)) return 1;
 
    return 0;
}
int main() {
    memset(dp,-1,sizeof(dp));
    scanf("%d %d\n",&N,&K);
    cin >> str;
    
    if(!go(0, K)) return !printf("NO");
 
    ans[sz(str)] = 0;
    printf("%s",ans);
    return 0;
}