803E - Roma and Poker
?
思路：
codeforces排名？ 贏或輸或者平的序列；
贏和平的差的絕對值不得超過k；
結束時差的絕對值必須為k；
當“？”時可以自己決定為什么狀態；
codeforces中文官網？ 輸出最終序列或者NO；
dp（隨便搞搞）；
?
來，上代碼：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;int n,k,dp[1005][2005],m;char ch[1005];int main() {cin>>n>>k;cin>>ch+1;m=k-1;dp[0][m+1]=true;for(int i=1;i<n;i++){if(ch[i]=='W') for(int j=2;j<=m*2+1;j++) dp[i][j]=dp[i-1][j-1];else if(ch[i]=='L') for(int j=1;j<m*2+1;j++) dp[i][j]=dp[i-1][j+1];else if(ch[i]=='D') for(int j=1;j<=m*2+1;j++) dp[i][j]=dp[i-1][j];else for(int j=1;j<=m*2+1;j++) dp[i][j]=(dp[i-1][j-1]||dp[i-1][j]||dp[i-1][j+1]);}if(ch[n]=='W') dp[n][2*m+2]=dp[n-1][2*m+1];else if(ch[n]=='L') dp[n][0]=dp[n-1][1];else if(ch[n]=='D') ;else dp[n][0]=dp[n-1][1],dp[n][m*2+2]=dp[n-1][m*2+1];if(!dp[n][0]&&!dp[n][m*2+2]) cout<<"NO";else{int now;if(dp[n][m*2+2]) now=m*2+2;else now=0;for(int i=n;i>0;i--){if(ch[i]=='L') now++;else if(ch[i]=='W') now--;else if(ch[i]=='D') now=now;else{if(dp[i-1][now+1]) now++,ch[i]='L';else if(dp[i-1][now]) ch[i]='D';else if(dp[i-1][now-1]) now--,ch[i]='W';}}cout<<ch+1;}return 0; }
?
