题目链接：http://codeforces.com/contest/803/problem/E

题意：看比赛，W是赢，L是输，D是平，？不知道。现在一个人希望输和赢的数量差的绝对值为k，且比赛期间输赢数小于k，问可行方案。

dp(i,j)代表比赛i场W比L多j的数量，W的时候从dp(i-1,j-1)更新来，L的时候从dp(i-1,j+1)更新来，D从dp(i-1,j)更新。？的时候从任意一个1过来就行了。记录路径用个path(i,j)打1 0 -1标记，往回找的时候直接插到字符串里，逆序输出即可。

显然-k<=j<=k。数组下标不能找到负数，于是偷懒用unordered_map，不过听说比赛期间这么写会被卡hash撞车cha= =

1 #include 
     
       2 using namespace std; 3  4 const int maxn = 1010; 5 int n, k; 6 char s[maxn]; 7 unordered_map
      
        dp[maxn], path[maxn]; 8  9 int main() {10     // freopen("in", "r", stdin);11     // freopen("out", "w", stdout);12     while(~scanf("%d%d",&n,&k)) {13         for(int i = 1; i <= n; i++) {14             dp[i].clear(); path[i].clear();15         }16         scanf("%s", s+1);17         dp[0][0] = 1;18         for(int i = 1; i <= n; i++) {19             for(int j = -k; j <= k; j++) {20                 if(i != n && (j == -k || j == k)) continue; 21                 if(s[i] == 'L') {22                     dp[i][j] = dp[i-1][j+1];23                     path[i][j] = 1;24                 }25                 if(s[i] == 'W') {26                     dp[i][j] = dp[i-1][j-1];27                     path[i][j] = -1;28                 }29                 if(s[i] == 'D') {30                     dp[i][j] = dp[i-1][j];31                     path[i][j] = 0;32                 }33                 if(s[i] == '?') {34                     if(dp[i][j] < dp[i-1][j+1]) {35                         dp[i][j] = dp[i-1][j+1];36                         path[i][j] = 1;37                     }38                     if(dp[i][j] < dp[i-1][j-1]) {39                         dp[i][j] = dp[i-1][j-1];40                         path[i][j] = -1;41                     }42                     if(dp[i][j] < dp[i-1][j]) {43                         dp[i][j] = dp[i-1][j];44                         path[i][j] = 0;45 46                     }47                 }48             }49         }50         if(dp[n][k] + dp[n][-k] == 0) {51             puts("NO");52             continue;53         }54         string tmp;55         int j = dp[n][k] ? k : -k;56         for(int i = n; i >= 1; i--) {57             if(path[i][j] == 0) tmp += 'D';58             else if(path[i][j] == 1) tmp += 'L';59             else if(path[i][j] == -1) tmp += 'W';60             j += path[i][j];61         }62         for(int i = tmp.length() - 1; i >= 0; i--) printf("%c", tmp[i]);63         printf("\n");64         65     }66     return 0;67 }