Educational Codeforces Round 20 E - Roma and Poker（dp）

传送门

题意

Roma在玩一个游戏，一共玩了n局，赢则bourle+1，输则bourle-1，Roma将会在以下情况中退出

1.他赢了k个bourle

2.他输了k个bourle

现在给出一个字符串

'L':lose

'W':win

'?':任意

'D':平局

输出一个字符串满足条件（Roma n局后离开要满足上述两个其中之一）

分析

dp题

令dp[i][j]表示进行i-1局比赛后，是否获得j个bourle。

如果第i局为'W'： dp[i+1][j+1]=j;

如果第i局为'L'：dp[i+1][j-1]=j;

如果第i局为'D'：dp[i+1][j]=j;

如果第i局为'?':上面三个都要进行

一开始dp[0][1500]=0

最后从n-1到0，比较dp[i][f]与f,f一开始是1500±k，f=dp[i+1][f]

回溯判断输出

trick

代码

#include<cstdio>

#include<string>

#include<iostream>

#include<algorithm>

using namespace std;

string s;

int dp[1010][3030];

int n,k;

int main()

{

    cin>>n>>k>>s;

    for(int i=0;i<1010;++i)for(int j=0;j<3030;++j) dp[i][j]=-1;

    dp[0][1500]=0;

    for(int i=0;i<n;++i)

        for(int j=1500-k+1;j<=1500+k-1;++j)

        {

            if(dp[i][j]==-1)continue;

            if(s[i]=='W'||s[i]=='?') dp[i+1][j+1]=j;

            if(s[i]=='L'||s[i]=='?') dp[i+1][j-1]=j;

            if(s[i]=='D'||s[i]=='?') dp[i+1][j]=j;

        }

        if(dp[n][1500+k]==-1&&dp[n][1500-k]==-1) { puts("NO");return 0; }

        int f=1500+k;

        if(dp[n][1500+k]==-1) f=1500-k;

        for(int i=n-1;i>=0;--i)

        {

            int g=f;f=dp[i+1][f];

            if(g-f==1) s[i]='W';

            if(g-f==0) s[i]='D';

            if(g-f==-1) s[i]='L';

        }

        cout<<s<<endl;

        return 0;

}

巴特西

Educational Codeforces Round 20 E - Roma and Poker（dp）

传送门

题意

分析

trick

代码

最新文章

热门文章