主要思路

概率 DP，显然地。

我们怎么来统计呢？在存下概率之后，我们枚举轮数并且枚举硬币向上的情况，之后转移即可，代码里一目了然。

代码

// I.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3030;
int n;
double prob[MAX_N], dp[MAX_N][MAX_N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &prob[i]);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= i; j++)
        {
            int x = j, y = i - j;
            if (x)
                dp[x][y] += dp[x - 1][y] * prob[i];
            if (y)
                dp[x][y] += dp[x][y - 1] * (1 - prob[i]);
        }
    double ans = 0;
    for (int i = 0; n - i > i; i++)
        ans += dp[n - i][i];
    printf("%.10lf", ans);
    return 0;
}

主要思路

啊呀，我太菜了。

因为每盘的寿司数量最多为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;
}

主要思路

这道题比较有趣，一开始我想出了\(O(n^3)\)的复杂度，打上去 TLE 之后思考前缀做差的方法，但是我太 Naive，不太相信（？）模意义下的减法，所以这个思路在我看了题解之后才搞定。

这道题的 DP 方程不难想到，为：

\[ dp[u][i] = \sum_{t \in dst} \sum_{j \in color(t)} dp[t][j], i \neq j \]

其实我们可以把第二维消掉，考虑总和\(tot[]\)数组，得：

\[ dp[u][i] = \sum_{t \in dst} tot[t] – dp[t][i] \]

然后就出来了。

代码

// P3914.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050, MOD = 1e9 + 7;
int head[MAX_N], current, n, m, tmpx, tmpy, dp[MAX_N][MAX_N], tot[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void dfs(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u);
    for (int i = 1; i <= m; i++)
    {
        if (!dp[u][i])
            continue;
        for (int e = head[u]; e != -1; e = edges[e].nxt)
        {
            if (edges[e].to == fa)
                continue;
            dp[u][i] = (1LL * dp[u][i] * 1LL * (tot[edges[e].to] - dp[edges[e].to][i])) % MOD;
        }
        while (dp[u][i] < 0)
            dp[u][i] += MOD;
        tot[u] = (1LL * tot[u] + 1LL * dp[u][i]) % MOD;
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmpy);
        for (int j = 1; j <= tmpy; j++)
            scanf("%d", &tmpx), dp[i][tmpx] = 1;
    }
    for (int i = 1; i < n; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    dfs(1, 0);
    printf("%d", tot[1] % MOD);
    return 0;
}

主要思路

这道题算是非常的毒瘤了。

首先我们来看第一问，根据 XG 巨佬的话，是非常明显的。我们在序列读入时减去元素自己的序号，找 LIS 长度即可。代码：

scanf("%lld", &n);
for (ll i = 1; i <= n; i++)
    scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
for (ll i = 2; i <= n; i++)
{
    ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
    len = max(len, addr);
    dp[i] = addr;
    dst[addr] = min(dst[addr], arr[i]);
}
printf("%lld\n", n - dp[n]);

第二问我们引出一个小的结论：如果要把区间\([l\dots r]\)之间变得“好看”，那么这个子区间内一定分为两段：高度为\(arr[l]\)的一段和高度\(arr[r]\)的一段。注意，此时\(arr[]\)内的元素已经剪去了元素编号。

所以这第二问就是一道区间 DP，时间复杂度为\(O(n^3)\)。不过好在序列随机，且我们可以使用邻接表预先存好那些可以处理的区间，然后进行 DP。

代码

// P2501.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll MX_N = 35020, INF = 0x3f3f3f3f;
ll head[MX_N], arr[MX_N], n, len, dst[MX_N], dp[MX_N], M_curt, f[MX_N], sum1[MX_N], sum2[MX_N];
struct edge
{
    ll to, nxt;
} edges[MX_N << 1];
void addpath(ll src, ll dst)
{
    edges[M_curt].to = dst, edges[M_curt].nxt = head[src];
    head[src] = M_curt++;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
    dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
    for (ll i = 2; i <= n; i++)
    {
        ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
        len = max(len, addr);
        dp[i] = addr;
        dst[addr] = min(dst[addr], arr[i]);
    }
    printf("%lld\n", n - dp[n]);
    for (ll i = n; i >= 0; i--)
        addpath(dp[i], i), f[i] = INF;
    f[0] = 0;
    for (ll i = 1; i <= n; i++)
        for (ll e = head[dp[i] - 1]; e != -1; e = edges[e].nxt)
        {
            ll v = edges[e].to;
            if (v > i)
                break;
            if (arr[v] > arr[i])
                continue;
            for (ll k = v; k <= i; k++)
                sum1[k] = abs(arr[k] - arr[v]), sum2[k] = abs(arr[k] - arr[i]);
            for (ll k = v + 1; k <= i; k++)
                sum1[k] += sum1[k - 1], sum2[k] += sum2[k - 1];
            for (ll k = v; k <= i - 1; k++)
                f[i] = min(f[i], f[v] + sum1[k] - sum1[v] + sum2[i] - sum2[k]);
        }
    printf("%lld", f[n]);
    return 0;
}