Luogu T103187 东方CannonBall 概率dp

题目背景

东方CannonBall（译名东方大炮弹）是近期发布的第一款获得ZUN授权的商业东方二次创作手机游戏，游戏关卡中玩家在类似大富翁的棋盘上与CPU或是玩家进行对战。

题目描述

在游戏中，每位玩家拥有若干个六面骰子。当两名玩家相遇时，将会通过掷出所有骰子的方式判定胜负。你拥有

正式地说，将玩家的 $nn个骰子编号为1..n1..n，在每次掷骰子时，第ii个骰子的点数a_iai会在{1,2,3,4,5,6}{1,2,3,4,5,6}中等概率随机选取，玩家的点数和C_n=sum_{1le i le n} a_iCn=∑1≤i≤nai，求P(C_x>C_y)P(Cx>Cy)$

输入格式

一行2个整数，依次表示你的骰子数

输出格式

一行一个百分数，四舍五入保留小数点后2位小数，表示你的胜率。

输入输出样例

输入 #1

1 1

输出 #1

41.67%

输入 #2

500 499

输出 #2

52.22%

说明/提示

对于样例1，双方有 $frac {1} {6}$

本题使用文本方式比较

数据规模

对于 $30\%30% 的数据，保证 x+y le 8x+y≤8。$

对于 $60\%60% 的数据，保证 x,y le 10x,y≤10$

对于 $100\%100% 的数据，保证 1 le x, yleq 10001≤x,y≤1000$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 typedef long long ll;
 8 
 9 ll read(){
10     ll a = 0; char l = ' ',c = getchar();
11     while(c < '0'||c > '9')l = c,c = getchar();
12     while('0' <= c&&c <= '9')a = a*10+c-'0',c = getchar();
13     if(l == '-')return -a; return a;
14 }
15 
16 ll f[2][2][6010],s[2][6010];
17 ll x,y,win,tot;
18 
19 int main(){
20     x = read(),y = read();
21 //    for(int i = 1;i <= 6;i++)f[0][0][i] = f[0][1][i] = 1;
22     f[0][0][0] = f[0][1][0] = 1;
23     for(int i = 1;i <= x;i++){
24         memset(f[i&1][0],0,sizeof(f[i&1][0]));
25         for(int j = x*6;j >= 0;j--)if(f[~i&1][0][j])
26             for(int k = 1;k <= 6;k++)
27                 f[i&1][0][j+k] += f[~i&1][0][j];
28     }
29     for(int i = 1;i <= y;i++){
30         memset(f[i&1][1],0,sizeof(f[i&1][1]));
31         for(int j = y*6;j >= 0;j--)if(f[~i&1][1][j]){
32 //            printf("%d ",f[~i&1][1][j]);
33             for(int k = 1;k <= 6;k++)
34                 f[i&1][1][j+k] += f[~i&1][1][j];
35         }//putchar('
');
36     }
37 //    for(int i = 1;i <= x*6;i++)
38 //        s[0][i] = s[0][i-1]+f[0][i];
39 //    for(int i = 1;i <= y*6;i++)
40 //        s[1][i] = s[1][i-1]+f[y&1][1][i];
41     for(int i = x;i <= x*6;i++){
42         ll cur = 0;
43         for(int j = y;j < i;j++)cur += f[x&1][0][i]*f[y&1][1][j];
44         win += cur;
45         for(int j = i;j <= y*6;j++)cur += f[x&1][0][i]*f[y&1][1][j];
46         tot += cur;
47     }
48     
49 //    cout << win << ' ' << tot << endl;
50 //    for(int i = 0;i <= x*6;i++)printf("%d ",f[x&1][0][i]);putchar('
');
51 //    for(int i = 0;i <= y*6;i++)printf("%d ",f[y&1][1][i]);putchar('
');
52     
53     double ans = 1.0*win/tot*100;
54     printf("%.2f%%",ans);
55 return 0;
56 }

60分代码