Kalorona

Educational DP Contest : J – Sushi 题解

主要思路

啊呀，我太菜了。

因为每盘的寿司数量最多为3，所以我们可以三个参数分别代表寿司数量为\(i\)的盘数。然后我们可以得出这样的方程：

\[ tot = A + B + C, dp(A,B,C) = \frac{n}{tot} + \frac{A}{tot}*dp(A-1,B,C) + \frac{B}{tot}*dp(A+1,B-1,C) + \frac{C}{tot}*dp(A,B+1,C-1) \]

因为没有固定的顺序进行 DP，所以我们进行记忆化搜索即可。

代码

// J.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 330;
int n, ai[MAX_N], sushi[4];
double dp[MAX_N][MAX_N][MAX_N];
double dfs(int a, int b, int c)
{
    if (a == 0 && b == 0 && c == 0)
        return 0;
    if (dp[a][b][c] >= 0)
        return dp[a][b][c];
    double d = a + b + c, ans = n / d;
    if (a)
        ans += dfs(a - 1, b, c) * a / d;
    if (b)
        ans += dfs(a + 1, b - 1, c) * b / d;
    if (c)
        ans += dfs(a, b + 1, c - 1) * c / d;
    return dp[a][b][c] = ans;
}
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), sushi[ai[i]]++;
    printf("%.10lf", dfs(sushi[1], sushi[2], sushi[3]));
    return 0;
}

「Codeforces 280C」Game on Tree 题解

主要思路

我们考虑每一个点被删掉的情景，对于点\(i\)，它只能被深度小于等于点\(i\)的点操作后删除，概率为\(\frac{1}{dep[i]}\)，每删掉一个节点的代价是\(1\)，所以答案为\(\sum_{i=1}^{n} \frac{1}{dep[i]}\)

代码

// CF280C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 100;
int head[MAX_N], current, n, tmpx, tmpy;
double ans = 0;
struct edge
{
	int to, nxt;
} edges[MAX_N << 1];
void addpath(int u, int v)
{
	edges[current].to = v, edges[current].nxt = head[u];
	head[u] = current++;
}
void dfs(int u, int fa, int dep)
{
	ans += 1.0 / dep;
	for(int i = head[u]; i != -1; i = edges[i].nxt)
		if(edges[i].to != fa)
			dfs(edges[i].to, u, dep + 1);
}
int main()
{
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	for(int i = 1; i <= n - 1; i++)
		scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
	dfs(1, 0, 1);
	printf("%.20lf", ans);
	return 0;
}