S+ 期望与概率
A. 骰子游戏
1 | const int N = 2e3 + 10; |
B. 真人秀
- 其实用 DFS + 记忆化 去写更清楚
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39signed main()
{
IOS;
int n, m;
while (cin >> n >> m) {
vector<vector<double> > DP(n + 1, vector<double>(m + 1, 0.0));
DP[n][m] = 1.0;
for (int i = n; i > 0; i--) {
for (int j = m; j >= 0; j--) {
int op = i;
if (i >= 2) {
op += (i * (i - 1)) / 2;
}
if (j > 0) {
op += i * j;
}
if (i >= 2)
{ // langlang
DP[i - 2][j] += DP[i][j] * ((i * (i - 1)) / 2) / (1.0 * op);
}
if (j > 0) { // langlu
DP[i][j - 1] += (DP[i][j] * j * i) / (1.0 * op);
}
//cout << DP[i][j] << ' ';
}
//cout << endl;
}
double ans = 0.0;
for (int i = 0; i <= m; i++)
{
ans += DP[0][i];
//cout << DP[0][i] << ' ';
}
//cout << endl;
cout << fixed << setprecision(6) << ans << endl;
}
return 0;
}
C. 排列价值
- 这叫期望的线性性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24const int N=1e3+10;
int w[N];
int n;
void solve()
{
for(int i=1;i<=n;i++) cin>>w[i];
double res=0;
for(int i=1;i<=n;i++)
{
double p;
if(i==1 || i==n) p=(double)1/2;
else p=(double)1/3;
res+=(double)p*w[i];
}
cout<<fixed<<setprecision(6)<<res<<"\n";
}
signed main()
{
while(cin>>n) solve();
return 0;
}
D. 字符串的价值
还是利用期望的线性性，1，2还好求，3不好求
1 | int n; |
E. 真人秀2
- 这是利用终态逆推出来的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29const int maxn = 1010;
int t, d;
double f[maxn][maxn];
double dp(int n, int m) { //n个老虎,m个鹿
if(n <= 0) {
return 0.0;
}
if(n == 1 && m == 0) {
return 1.0;
}
if(f[n][m] >= 0) {
return f[n][m];
}
int tot = (n + m + 1) * (n + m) / 2;
double &v = f[n][m];
v = 0;
if(m >= 1) {
v += dp(n, m - 1) * 1.0 * n * m / tot;
}
v += dp(n - 2, m) * 1.0 * n * (n - 1) / 2 / tot;
v = (v + 1) / (1.0 - 1.0 * (m + 1) * m / 2 / tot);
return f[n][m];
}
int main() {
scanf("%d%d", &t, &d);
memset(f, -1, sizeof f);
printf("%.6lf\n", dp(t, d));
return 0;
}
F. 奖励关
- 利用终态的确定性去写的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31int k, n, limit[105];
double dp[105][1 << 15 | 1], p[105];
double dfs(int x, int y) {
if(dp[x][y] != -1) return dp[x][y];
//cout << x << " " << y << endl;
dp[x][y] = 0;
for (int i = n - 1; ~i; --i) {
if((limit[i] & y) ^ limit[i]) dp[x][y] += 1.0 / n * dfs(x + 1, y);
else dp[x][y] += 1.0 / n * max(dfs(x + 1, y | (1 << i)) + p[i], dfs(x + 1, y));
}
return dp[x][y];
}
int main() {
scanf("%d%d", &k, &n);
//cout << 1111 << endl;
for(int i = 0; i < n; ++i) {
scanf("%lf", p + i);
while(1) {
int a;
scanf("%d", &a);
if(!a) break;
limit[i] |= 1 << a - 1;
}
// cout << i << " " << p[i] << " " << limit[i] << endl;
}
//cout << 2222 << endl;
for(int i = k; i; --i) for(int j = (1 << n) - 1; ~j; --j) dp[i][j] = -1;
//cout << 3333 << endl;
printf("%.6lf", dfs(1, 0));
return 0;
}
G. 放棋子
- 还好的状态表示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31const int maxd=50+5;
int dx[]= {0,1,0,-1};
int dy[]= {1,0,-1,0};
int n,m;
double dp[maxd][maxd][maxd*maxd];
int main()
{
int kase;
scanf("%d",&kase);
while(kase--)
{
mem(dp,0);
dp[1][1][1]=1;
scanf("%d%d",&n,&m);
for(int k=1; k<=n*m; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
dp[i+1][j][k+1]+=(dp[i][j][k]* ((n-i)*j*1.0)/(n*m-k));
dp[i][j+1][k+1]+=(dp[i][j][k]* ((m-j)*i*1.0)/(n*m-k));
dp[i+1][j+1][k+1]+=(dp[i][j][k]* (n-i)*(m-j)*1.0/(n*m-k));
dp[i][j][k+1]+=(dp[i][j][k]* (i*j-k)*1.0/(n*m-k));
}
double ans=0.0;
for(int k=1;k<=n*m;k++)
ans+=(dp[n][m][k]-dp[n][m][k-1])*k;
printf("%.12lf\n",ans);
}
return 0;
}
H.扑克牌
- 用记忆话搜索DP就好了，因为状态只要是这个状态结果就相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53const int N = 14;
const double INF = 1e20;
int A, B, C, D;
double f[N][N][N][N][5][5];
double dp(int a, int b, int c, int d, int x, int y)
{
double &v = f[a][b][c][d][x][y];
if (v >= 0) return v;
int as = a + (x == 0) + (y == 0);
int bs = b + (x == 1) + (y == 1);
int cs = c + (x == 2) + (y == 2);
int ds = d + (x == 3) + (y == 3);
if (as >= A && bs >= B && cs >= C && ds >= D) return v = 0;
int sum = a + b + c + d + (x != 4) + (y != 4);
sum = 54 - sum;
if (sum <= 0) return v = INF;
v = 1;
if (a < 13) v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
if (b < 13) v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
if (c < 13) v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
if (d < 13) v += (13.0 - d) / sum * dp(a, b, c, d + 1, x, y);
if (x == 4)
{
double t = INF;
for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
v += t;
}
if (y == 4)
{
double t = INF;
for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
v += t;
}
return v;
}
int main()
{
cin >> A >> B >> C >> D;
memset(f, -1, sizeof f);
double t = dp(0, 0, 0, 0, 4, 4);
if (t > INF / 2) t = -1;
printf("%.3lf\n", t);
return 0;
}
I. 换教室
- 虽然很长，但本质就是线性DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using namespace std;
const int VM=305,EM=90005;
int n,m,v,e;
struct edge {
int v,c,to;
} E[EM<<1];
int head[VM],e_tot;
void Link(int u,int v,int c) {
E[++e_tot]=(edge) {
v,c,head[u]
};
head[u]=e_tot;
}
int Dist[VM][VM];
void Floyd() {//最短路板子
for(int u=1; u<=v; u++)
for(int w=0; w<u; w++)
Dist[u][w]=Dist[w][u]=1e9;
for(int u=1; u<=v; u++)
for(int i=head[u]; i!=0; i=E[i].to) {
int w=E[i].v,c=E[i].c;
Dist[u][w]=min(Dist[u][w],c);
}
for(int q=1; q<=v; q++)
for(int i=1; i<=v; i++)
for(int j=1; j<=v; j++)
Dist[i][j]=min(Dist[i][j],Dist[i][q]+Dist[q][j]);
}
int C[2005],D[2005];
double K[2005];
int Shrt[2][2][2005];
void Init_Shrt() {//预处理最短路
Floyd();
for(int i=2; i<=n; i++) {
Shrt[0][0][i]=Dist[C[i-1]][C[i]];
Shrt[0][1][i]=Dist[C[i-1]][D[i]];
Shrt[1][0][i]=Dist[D[i-1]][C[i]];
Shrt[1][1][i]=Dist[D[i-1]][D[i]];
}
}
double dp[2][2005][2005];
void Solve() {
Init_Shrt();
for(int i=1; i<=n; i++)
for(int j=0; j<=m; j++)
dp[0][i][j]=2e18,dp[1][i][j]=2e18;
dp[0][1][0]=dp[1][1][1]=dp[0][1][1]=0;
for(int i=2; i<=n; i++) {
dp[0][i][0]=dp[0][i-1][0]+Shrt[0][0][i];
for(int j=1; j<=m&&j<=i; j++) {
dp[0][i][j]=//注意排版，利于debug。这个排版还是比较清楚的
min(
dp[1][i-1][j]+(
K[i-1] *Shrt[1][0][i]+//前一次申请成功
(1-K[i-1])*Shrt[0][0][i] //前一次申请失败
),
dp[0][i-1][j]+Shrt[0][0][i] //两次都没申请
);
dp[1][i][j]=
min(
dp[1][i-1][j-1]+(
K[i-1] *K[i] *Shrt[1][1][i]+//两次都成功
K[i-1] *(1-K[i])*Shrt[1][0][i]+//前一次成功，这次失败
(1-K[i-1])*K[i] *Shrt[0][1][i]+//前一次失败，这次成功
(1-K[i-1])*(1-K[i])*Shrt[0][0][i] //两次都失败
),
dp[0][i-1][j-1]+(
K[i] *Shrt[0][1][i]+//这次成功
(1-K[i])*Shrt[0][0][i] //这次失败
));
}//可以看到主要是用期望的定义暴力算的
}
double ans=2e18;
for(int i=0; i<=m; i++)ans=min(ans,min(dp[0][n][i],dp[1][n][i]));
printf("%.2lf
",ans);
}
int main() {
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1; i<=n; i++)scanf("%d",&C[i]);
for(int i=1; i<=n; i++)scanf("%d",&D[i]);
for(int i=1; i<=n; i++)scanf("%lf",&K[i]);
for(int i=1; i<=e; i++) {
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
Link(u,v,c);
Link(v,u,c);
}
Solve();
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ysmmm的快乐小屋！
