Gym102470 (SWERC 2009) D. Darts题解


D. Darts

题意:在指定的飞镖盘上有数字1~20,玩家A随机(1/20)扔飞镖,玩家B可以选择连续的三块等概率(1/3)扔飞镖。若A扔出的数字为

k

k

k,A的得分为

a

a

a,B的得分为

b

b

b,则此时

b

=

k

b-=k

b−=k,若

k

>

b

k>b

k>b就当无事发生,当且仅当

k

=

b

k=b

k=b时A获胜;B的回合同理。求玩家A和B分别先手的胜率。

解析:经典概率dp,设

f

[

0

/

1

]

[

i

]

[

j

]

f[0/1][i][j]

f[0/1][i][j]为该A/B扔飞镖时,A还剩

i

i

i分,B还剩

j

j

j分时A/B的胜率,显然有转移:

f

[

0

]

[

i

]

[

j

]

=

(

1

f

[

1

]

[

i

]

[

j

p

[

1…20

]

]

)

20

f[0][i][j]=\frac{\sum{(1-f[1][i][j-p[1…20]])}}{20}

f[0][i][j]=20∑(1−f[1][i][j−p[1…20]])​

f

[

1

]

[

i

]

[

j

]

=

max

{

(

1

f

[

0

]

[

i

p

[

k

/

k

+

1

/

k

+

2

]

]

[

j

]

)

}

3

f[1][i][j]=\frac{\max\{\sum{(1-f[0][i-p[k/k+1/k+2]][j])}\} }{3}

f[1][i][j]=3max{∑(1−f[0][i−p[k/k+1/k+2]][j])}​

然而要是这么简单就结束了,过的人不会这么少(

实际上,当

i

20

j

20

i\le20||j\le20

i≤20∣∣j≤20时,情况发生了微妙的改变,

首先,显然

i

20

&

&

j

20

i\le20\&\&j\le20

i≤20&&j≤20时,答案都是确定的,这里样例里的

n

=

5

n=5

n=5给出了结果,

在转移的时候,由于

p

[

k

]

>

a

p[k]>a

p[k]>a无事发生,就会存在

f

[

0

]

[

i

]

[

j

]

f[0][i][j]

f[0][i][j]到

f

[

1

]

[

i

]

[

j

]

f[1][i][j]

f[1][i][j]的转移以及

f

[

1

]

[

i

]

[

j

]

f[1][i][j]

f[1][i][j]到

f

[

0

]

[

i

]

[

j

]

f[0][i][j]

f[0][i][j]的转移,

啊这,成环了该怎么dp啊?

但是观察发现,其实只有

f

[

0

]

[

i

]

[

j

]

f[0][i][j]

f[0][i][j]和

f

[

1

]

[

i

]

[

j

]

f[1][i][j]

f[1][i][j]之间的相互转移,也就是说只存在两个未知数,

那么问题就解决了,怎么办?解方程!

A

=

f

[

0

]

[

i

]

[

j

]

,

 

B

=

f

[

1

]

[

i

]

[

j

]

A=f[0][i][j],\ B=f[1][i][j]

A=f[0][i][j], B=f[1][i][j],则有

A

=

t

1

+

c

1

(

1

B

)

A=t_1+c_1(1-B)

A=t1​+c1​(1−B)

B

=

t

2

+

c

2

(

1

A

)

B=t_2+c_2(1-A)

B=t2​+c2​(1−A)

而且,由于B可以选择投掷策略,我们就先解出

B

B

B的值,易得

B

=

t

2

+

c

2

t

1

c

2

c

1

c

2

1

c

1

c

2

B=\frac{t_2+c_2-t_1c_2-c_1c_2}{1-c_1c_2}

B=1−c1​c2​t2​+c2​−t1​c2​−c1​c2​​

t

1

,

t

2

,

c

1

,

c

2

t_1,t_2,c_1,c_2

t1​,t2​,c1​,c2​都可以在循环里求出来,取最大值就能得到

B

B

B即

f

[

1

]

[

i

]

[

j

]

f[1][i][j]

f[1][i][j]了,问题就这么愉快的解决了。

代码:

#include<bits/stdc++.h>
#define db long double
#define _S(...) scanf(__VA_ARGS__)
#define _P(...) printf(__VA_ARGS__)
#define GKD ios::sync_with_stdio(false)
using namespace std;
const db EPS=1e-8;
const int N=520;
const int LIM=501;
const int p[20]={1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5,20};
int n;
db f[2][N][N];//0:A, 1:B
int main()
{
for(int i=1;i<=20;i++)
{
f[0][0][i]=f[1][i][0]=0;
f[1][0][i]=f[0][i][0]=1;
}
for(int i=1;i<=20;i++)
{
for(int j=1;j<=20;j++)
{
f[0][i][j]=0.136363636364;
f[1][i][j]=0.909090909091;
}
}
for(int i=1;i<=LIM;i++)
{
for(int j=1;j<=LIM;j++)
{
if(i<=20&&j<=20)continue;
db c1=0,c2=0,t=0,t1=0,t2=0;
for(int k=0;k<20;k++)//A-go
{
if(j-p[k]<0)c1++;
else t1+=(1.0-f[1][i][j-p[k]]);
}
c1/=20.0,t1/=20.0;
for(int k=0;k<20;k++)//B-go
{
c2=t2=0;
for(int l=0;l<3;l++)
{
if(i-p[(k+l)%20]<0)c2++;
else t2+=(1.0-f[0][i-p[(k+l)%20]][j]);
}
c2/=3.0,t2/=3.0;
t=max(t,(t2+c2-t1*c2-c1*c2)/(1-c1*c2));
}
f[1][i][j]=t;
f[0][i][j]=t1+c1*(1.0-t);
}
}
GKD;
while(_S("%d", &n), n)
{
_P("%.12Lf %.12Lf\n",f[0][n][n],f[1][n][n]);
}
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

Gym102470 (SWERC 2009) D. Darts题解

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » Gym102470 (SWERC 2009) D. Darts题解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏