原題鏈接：http://codeforces.com/problemset/problem/803/E
?
題意：給一個n長度的字符串，其中'?'可以替換成'D'、'W'、'L'中的任意一種，'D'等價于0,?'W'等價于1、'L'等價于-1。輸出所有'?'被替換掉后，W和L的數目之差為k，且任意一個[1, i]的子串中W和L數目之差不能等于k。
?
思路：用DP做。定義bool dp[i][j]代表前i個字符W和L數目之差為j, -k<=j<=k(在數組中范圍為[0, 2*k])，那么當str[i]為'D'時dp[i][j]轉移到dp[i-1][j],?為'W'時dp[i][j]轉移到dp[i-1][j+1], str[i]為'D'時dp[i][j]轉移到dp[i-1][j-1], 初始值dp[0][0]為true。
接著用一遍dfs倒推求結果，注意字符加的位置。
?
AC代碼：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 using namespace std; 6 int dp[2005][4005]; 7 int n,k; 8 string str; 9 void change(int i, int L, int D, int W){ 10 for(int j=1;j<2*k;j++){ 11 if(dp[i-1][j]){ 12 if(D) dp[i][j]=1; 13 if(L){ 14 if(i!=n&&j-1==0)//[1, i]子串中W和L數目之差不能等于k 15 continue; 16 dp[i][j-1]=1; 17 } 18 if(W){ 19 if(i!=n&&j+1==2*k) 20 continue; 21 dp[i][j+1]=1; 22 } 23 } 24 } 25 return; 26 } 27 string ss; 28 //int t=0; 29 bool res(int i, int j, string ans){ 30 //t++; 31 if(i==0&&j==k){ 32 ss=ans; 33 return 1; 34 } 35 if(str[i-1]!='?'){ 36 if(str[i-1]=='D') return res(i-1, j, 'D'+ans); 37 if(str[i-1]=='W') return res(i-1, j-1, 'W'+ans); 38 if(str[i-1]=='L') return res(i-1, j+1, 'L'+ans); 39 } 40 else 41 { 42 if(dp[i-1][j]&&res(i-1, j, 'D'+ans)) return 1; 43 if(dp[i-1][j-1]&&res(i-1, j-1, 'W'+ans)) return 1; 44 if(dp[i-1][j+1]&&res(i-1, j+1, 'L'+ans)) return 1; 45 } 46 47 return 0; 48 } 49 int main() 50 { 51 while(cin>>n>>k) 52 { 53 memset(dp, 0, sizeof(dp)); 54 dp[0][k]=1; 55 cin>>str; 56 if(str[n-1]=='D'){ 57 cout<<"NO"<<endl; 58 continue; 59 } 60 for(int i=1;i<=n;i++){ 61 if(str[i-1]=='?') 62 change(i, 1, 1, 1); 63 else if(str[i-1]=='D') 64 change(i, 0, 1, 0); 65 else if(str[i-1]=='W') 66 change(i, 0, 0, 1); 67 else 68 change(i, 1, 0, 0); 69 } 70 string ans; 71 if(dp[n][0]){ 72 res(n, 0, ans); 73 cout<<ss<<endl; 74 } 75 else if(dp[n][2*k]){ 76 res(n, 2*k, ans); 77 cout<<ss<<endl; 78 } 79 else 80 cout<<"NO"<<endl; 81 //cout<<t<<endl; 82 } 83 return 0; 84 }
這代碼調了我好久啊QAQ，感覺自己真菜
?
)
