首页 > 代码库 > codeforces 830E dp
codeforces 830E dp
大致题意：
n场比赛，k个钱币。赢一场获得一个钱币，输一场失去一个钱币，一旦钱币数量为2k个或者0个，就马上离开比赛。给出n个长度字符串，由W,D,L,?四个字符组成，W表示赢，L表示输，D表示平局，?表示前三种情况的一种。
问此字符串是否是合法的赛事，如果合法，输出其中任意一种情况。
分析：
状态定义：d[i][j]表示前i场比赛，W-L=j，是否合法，合法为1，不合法为0
状态转移：if(s[i]==‘D‘) d[i][j]=d[i-1][j];
else if(s[i]==‘W‘) d[i][j]=d[i-1][j-1];
else if(s[i]==‘L‘) d[i][j]=d[i-1][j+1];
else d[i][j]=max(max(d[i-1][j-1],d[i-1][j+1]),d[i-1][j]);
输出路径从尾至头遍历，因为当前状态合法，必定会有一个可转移至当前状态的之前的状态也合法，注意下赢输的差值不要为边界值就行了。
#include <bits/stdc++.h>using namespace std;const int maxn=1005;char s[maxn],ans[maxn];bool d[maxn][4*maxn];void print_path(int )int main(){// freopen("in.txt","r",stdin); int n,k; while(~scanf("%d%d",&n,&k)) { scanf("%s",s+1); int mid=2000; memset(d,0,sizeof(d)); d[0][mid]=1; for(int i=1; i<=n; i++) { for(int j=mid-k; j<=mid+k; j++) { if(i!=n && (j==mid-k || j==mid+k)) continue; if(s[i]==‘D‘) d[i][j]=d[i-1][j]; else if(s[i]==‘W‘) d[i][j]=d[i-1][j-1]; else if(s[i]==‘L‘) d[i][j]=d[i-1][j+1]; else d[i][j]=max(max(d[i-1][j-1],d[i-1][j+1]),d[i-1][j]); } } if(!d[n][mid-k] && !d[n][mid+k]) { printf("NO\n"); continue; } if(d[n][mid-k]) { int tmp=mid-k; ans[n+1]=0; for(int i=n; i>=1; i--) { if(s[i]!=‘?‘) { ans[i]=s[i]; if(s[i]==‘L‘) tmp++; else if(s[i]==‘W‘) tmp--; } else { if(d[i-1][tmp] && tmp!=mid-k && tmp!=mid+k) ans[i]=‘D‘; else if(d[i-1][tmp+1] && tmp+1>mid-k && tmp+1<mid+k) { ans[i]=‘L‘; tmp++; } else if(d[i-1][tmp-1] && tmp-1>mid-k && tmp-1<mid+k) { ans[i]=‘W‘; tmp--; } } } printf("%s\n",ans+1); continue; } if(d[n][mid+k]) { int tmp=mid+k; ans[n+1]=0; for(int i=n; i>=1; i--) { if(s[i]==‘L‘ || s[i]==‘W‘ || s[i]==‘D‘) { ans[i]=s[i]; if(s[i]==‘L‘) tmp++; else if(s[i]==‘W‘) tmp--; } else { if(d[i-1][tmp] && tmp!=mid-k && tmp!=mid+k) ans[i]=‘D‘; else if(d[i-1][tmp+1] && tmp+1>mid-k && tmp+1<mid+k) { ans[i]=‘L‘; tmp++; } else if(d[i-1][tmp-1] && tmp-1>mid-k && tmp-1<mid+k) { ans[i]=‘W‘; tmp--; } } } printf("%s\n",ans+1); } } return 0;}
codeforces 830E dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。