http://acm.hdu.edu.cn/showproblem.php?pid=5602
dp[1][i][j]表示轮到第二个人操作时,第一人总和i,第二人总和j,第一人胜的最小概率(因为每个人都是聪明的,所以选最小)。
dp[0][i][j]表示第一个人操作时,第一个人胜的最大概率。
先算dp[1],然后用dp[1]算dp[0],注意x==y的情况。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int vis[][][] = {};
double dp[][][];
char a[];int cal(char c)
{
switch(c)
{
case 'A': return ;
case 'T':
case 'J':
case 'K':
case 'Q': return ;
default: return c-'';
}
}double dfs1(int x,int y)
{
if(y > ) return ;
if(vis[][x][y]) return dp[][x][y];
double temp = ;
dp[][x][y] = x>y;
for(int i = ;i < ;i++) temp += dfs1(x,y+i)/;
temp += dfs1(x,y+)*/;
dp[][x][y] = min(dp[][x][y],temp);
vis[][x][y] = ;
return dp[][x][y];
}double dfs0(int x,int y)
{
if(x > ) return ;
if(vis[][x][y]) return dp[][x][y];
dp[][x][y] = dfs1(x,y);
double temp = ;
for(int i = ;i < ;i++) temp += dfs0(x+i,y)/;
temp += dfs0(x+,y)*/;
dp[][x][y] = max(dp[][x][y],temp);
vis[][x][y] = ;
return dp[][x][y];
}int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",a);
int first = ,second = ;
first += cal(a[]);
first += cal(a[]);
second += cal(a[]);
second += cal(a[]);
double ans = dfs0(first,second);
if(ans > 0.5) printf("YES\n");
else printf("NO\n");
}
return ;
}