Codeforces 436D. Pudding Monsters

题意：

有一条无限长的带子，上面画有格子，其中一些是特殊格。有一些格子上有布丁怪兽。如果若干个怪兽的位置相邻，那么它们就会连起来。你需要进行若干次操作。每一次操作中，你需要选定一个怪兽，然后把它和连着它的怪兽一起向左或向右移动，知道移动到无穷远或碰到其他的怪兽并连起来。最多可以覆盖多少特殊格呢？

题解：

首先，最优方案一定不会让某些怪移到无穷远，也不会先连起来再一起移动（这样可以分别移到最后的位置）。设$f_i$表示前$i$只怪兽，第$i$只不动的答案；$g_i$表示前$i$只怪兽的答案；$s(i, j)$表示$i$到$j$之间有多少特殊格；$a_i$表示第$i$个怪兽的位置。转移的话，$f_i$就是枚举左边有多少个怪兽靠过来，然后通过$g$转移。但这样是$O(n ^ 2)$的。注意到如果靠过来的这一大段的左边是非特殊格，那么它靠过来就是没有意义的。所以只需要枚举特殊格就好了。这样可以变成$O(nm)$的。$g_i$的转移类似。方程：$f_i = \max\{g_j + s(a_i - (i - j - 1), a_i)\}, g_j = \max\{f_i + s(a_i, a_i + (j - i))\} \cup \{g_{i - 1}\}$
还有一点就是一开始就连起来的情况。随便搞搞就好。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, a[100010], p[2010], f[100010], g[100010], l[100010], r[100010], cnt[200010];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &p[i]);
    sort(a + 1, a + 1 + n);
    sort(p + 1, p + 1 + m);
    for (int i = 1; i <= m; i++) cnt[p[i]] = 1;
    for (int i = 1; i <= 200000; i++) cnt[i] += cnt[i - 1];
    l[1] = 1;
    for (int i = 2; i <= n; i++)
        l[i] = a[i] == a[i - 1] + 1 ? l[i - 1] : i;
    r[n] = n;
    for (int i = n - 1; i > 0; i--)
        r[i] = a[i] == a[i + 1] - 1 ? r[i + 1] : i;/*
    for (int i = 1; i <= 10; i++)
        printf("%d ", cnt[i]);
    puts("");*/
    for (int i = 1; i <= n; i++)
    {
        if (cnt[a[i]] - cnt[a[i] - 1] == 1) f[i] = 1;
        f[i] += g[l[i] - 1];
        for (int j = 1; j <= m && p[j] < a[i]; j++)
        {
            int hh = i - (a[i] - p[j]);
            // printf("%d %d\n", j, hh);
            if (hh <= 0) continue;
            f[i] = max(f[i], g[l[hh] - 1] + cnt[a[i]] - cnt[p[j] - 1]);
        }
        g[i] = max({g[i], f[i], g[i - 1]});
        for (int j = m; j > 0 && p[j] > a[i]; j--)
        {
            int hh = i + (p[j] - a[i]);
            if (hh > n) continue;
            g[r[hh]] = max(g[r[hh]], f[i] + cnt[p[j]] - cnt[a[i]]);
        }
        /*
        printf("%d\n", f[i]);
        for (int j = 1; j <= n; j++)
            printf("%d ", g[j]);
        puts("");*/
    }
    printf("%d\n", g[n]);
}