$dp$。
$dp[type][i][j]$表示，前i个字符前缀和为$j$，第$i$个字符放的是$type$类型的能否实现，然后倒推回来就可以了。
#include#include #include #include #include using namespace std;char s[1010];int n,k;int dp[3][1010][2010];int ans[1010];int B = 1000;void work(int type,int pos,int sum){ ans[pos] = type; if(pos==1) return ; int E; if(type == 0) E=-1; //L else if(type == 1) E=1; //W else if(type == 2) E=0; //D for(int i=0;i<3;i++) { if(dp[i][pos-1][sum-E]==0) continue; work(i,pos-1,sum-E); return ; }}int main(){ scanf("%d%d",&n,&k); scanf("%s",s); memset(dp,0,sizeof dp); dp[0][0][B] = 1; dp[1][0][B] = 1; dp[2][0][B] = 1; for(int i=1;i<=n;i++) { if(s[i-1]=='?') { for(int j=B-k;j<=B+k;j++) { if(j+1<=B+k) dp[0][i][j] = max(dp[0][i][j],dp[0][i-1][j+1]); if(j+1<=B+k) dp[0][i][j] = max(dp[0][i][j],dp[1][i-1][j+1]); if(j+1<=B+k) dp[0][i][j] = max(dp[0][i][j],dp[2][i-1][j+1]); } for(int j=B-k;j<=B+k;j++) { if(j-1>=B-k) dp[1][i][j] = max(dp[1][i][j],dp[0][i-1][j-1]); if(j-1>=B-k) dp[1][i][j] = max(dp[1][i][j],dp[1][i-1][j-1]); if(j-1>=B-k) dp[1][i][j] = max(dp[1][i][j],dp[2][i-1][j-1]); } for(int j=B-k;j<=B+k;j++) { dp[2][i][j] = max(dp[2][i][j],dp[0][i-1][j]); dp[2][i][j] = max(dp[2][i][j],dp[1][i-1][j]); dp[2][i][j] = max(dp[2][i][j],dp[2][i-1][j]); } } else if(s[i-1] == 'L') { for(int j=B-k;j<=B+k;j++) { if(j+1<=B+k) dp[0][i][j] = max(dp[0][i][j],dp[0][i-1][j+1]); if(j+1<=B+k) dp[0][i][j] = max(dp[0][i][j],dp[1][i-1][j+1]); if(j+1<=B+k) dp[0][i][j] = max(dp[0][i][j],dp[2][i-1][j+1]); } } else if(s[i-1]=='W') { for(int j=B-k;j<=B+k;j++) { if(j-1>=B-k) dp[1][i][j] = max(dp[1][i][j],dp[0][i-1][j-1]); if(j-1>=B-k) dp[1][i][j] = max(dp[1][i][j],dp[1][i-1][j-1]); if(j-1>=B-k) dp[1][i][j] = max(dp[1][i][j],dp[2][i-1][j-1]); } } else { for(int j=B-k;j<=B+k;j++) { dp[2][i][j] = max(dp[2][i][j],dp[0][i-1][j]); dp[2][i][j] = max(dp[2][i][j],dp[1][i-1][j]); dp[2][i][j] = max(dp[2][i][j],dp[2][i-1][j]); } } if(i