hdu6494 dp

http://acm.hdu.edu.cn/showproblem.php?pid=6494

题意

一个长n字符串(n,1e4),'A'代表A得分,'B'代表B得分,'?'代表不确定,一局比赛先得11分获胜,10比10以后先得两分者获胜,问你他们最多能比多少局

题解

定义$dp[i][j][k]$为第i个字符j比k的最大局数
- 10比10: $dp[i][10][10] ->dp[i+1][9][9]$
- j=11 or k=11:$dp[i][j][k] + 1-> dp[i+1][0][0]$
- 其他情况:$dp[i][j][k] -> dp[i+1][j+1][k]or dp[i+1][j][k+1]

代码

#include<bits/stdc++.h>

#define MAXN 10005

using namespace std;

const int inf=1e9+5;

int T,dp[MAXN][20][20];

char s[MAXN];

struct N{int x,y,z;N(int x=0,int y=0,int z=0):x(x),y(y),z(z){}};

N cal(int i,int j){

    if(i==11||j==11)

        return N(0,0,1);

    else{

        if(i==10&&j==10)return N(9,9,0);

        else return N(i,j,0);

    }

}

int main(){

    cin>>T;

    while(T--){

        scanf("%s",s);

        memset(dp,-1,sizeof(dp));

        int n=strlen(s);

        dp[0][0][0]=0;

        for(int i=1;i<=n;i++){

            for(int j=0;j<=10;j++){

                for(int k=0;k<=10;k++){

                    if(dp[i-1][j][k]>=0){

                        if(s[i-1]=='A'||s[i-1]=='?'){

                            N tp=cal(j+1,k);

                            dp[i][tp.x][tp.y]=max(dp[i][tp.x][tp.y],dp[i-1][j][k]+tp.z);

                        }

                        if(s[i-1]=='B'||s[i-1]=='?'){

                            N tp=cal(j,k+1);

                            dp[i][tp.x][tp.y]=max(dp[i][tp.x][tp.y],dp[i-1][j][k]+tp.z);

                        }

                    }

                }

            }

        }

        int ans=0;

        for(int i=0;i<=10;i++)for(int j=0;j<=10;j++)ans=max(ans,dp[n][i][j]);

        printf("%d\n",ans);

    }

}

巴特西

hdu6494 dp

题意

题解

代码

最新文章

热门文章