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

最新文章

热门文章