当前位置：首页 > news >正文

大三第一周训练

news 来源：原创 2024/5/7 16:28:50

周三

前段时间没有写日报，而是写专题了

概率/期望dp专题_Alex Su (*^▽^*)的博客-CSDN博客

博弈论专题_Alex Su (*^▽^*)的博客-CSDN博客

现在觉得写日报才每天有收获感，有动力，于是又开始写日报

P3802 小魔女帕琪（手推概率）

这题就是手算，算出1~7触发的概率，再算一下2~8触发的概率，发现是一样的，然后就可以推出答案了

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

int main()
{
    double a[10], N;
    _for(i, 1, 7) scanf("%lf", &a[i]), N += a[i];

    double ans = (N - 6) * 5040;
    _for(i, 1, 7) ans *= a[i] / max(N - i + 1, 1.0); 
    printf("%.3f\n", ans);
   
	return 0;
}

P1850 [NOIP2016 提高组] 换教室（期望dp+floyed）

这题的期望比较特殊，它是比较独立的，概率不需要连乘

也就是说期望体现在两个相邻时间段之间的贡献。这个时候就不是那种比较经典的期望dp了。

细节上，注意初始化和边界问题。

floyed的时候注意自己自己到自己为0，我忽略了这个卡了很久。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 2e3 + 10;
const int M = 300 + 10;
int n, m, v, e, c[N], d[N], g[M][M];
double k[N], dp[N][N][2];

int main()
{
    scanf("%d%d%d%d", &n, &m, &v, &e);
    _for(i, 1, n) scanf("%d", &c[i]);
    _for(i, 1, n) scanf("%d", &d[i]);
    _for(i, 1, n) scanf("%lf", &k[i]);
    memset(g, 0x3f, sizeof g);
    while(e--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = g[b][a] = min(g[a][b], w);
    }

    _for(K, 1, v)
        _for(i, 1, v)
            _for(j, 1, v)
                g[i][j] = min(g[i][j], g[i][K] + g[K][j]);
    _for(i, 1, v) g[i][i] = 0;    //写弗洛伊德时记得要加上自己和自己为0
    
    _for(i, 0, n)
        _for(j, 0, m) 
            dp[i][j][0] = dp[i][j][1] = 1e9;
    dp[1][1][1] = dp[1][0][0] = 0;
    _for(i, 2, n)
        _for(j, 0, m)
        {
            int c1 = c[i - 1], c2 = c[i], d1 = d[i - 1], d2 = d[i];
            dp[i][j][0] = min(dp[i - 1][j][0] + g[c1][c2], dp[i - 1][j][1]
                        + k[i - 1] * g[d1][c2] + (1 - k[i - 1]) * g[c1][c2]);
            if(j > 0)
                dp[i][j][1] = min(dp[i - 1][j - 1][0] + k[i] * g[c1][d2] + (1 - k[i]) * g[c1][c2],
                         dp[i - 1][j - 1][1] + k[i - 1] * k[i] * g[d1][d2] + (1 - k[i - 1]) * k[i] * g[c1][d2] + 
                        k[i - 1] * (1 - k[i]) * g[d1][c2] + (1 - k[i - 1]) * (1 - k[i]) * g[c1][c2]);
        }
    
    double ans = 1e9;
    _for(i, 0, m) ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
    printf("%.2f\n", ans);
   
	return 0;
}