Kalorona

P2577:「ZJOI2005」午餐题解

主要思路

容易想出状态\(dp[i][j][k]\)代表前\(i\)个人在一号队列排\(j\)分钟及在二号队排\(k\)分钟的最小时间。然后发现\(k\)这一维可以直接消去，因为有\(k=sum[i]-j\)。所以把线性依赖消去后，方程就非常小清新了：

\[dp[i][j] = min\{dp[i][j], max\{dp[i – 1][j – persons[i].a], j + persons[i].b\}\},当persons[i].a\leq j\]

\[dp[i][j] = min\{dp[i][j], max\{dp[i – 1][j], sum[i] – j + persons[i].b\}\}\]

代码

// P2577.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int MX_N = 220;
struct person
{
    ll a, b;
    bool operator<(const person &ps) const
    {
        return b > ps.b;
    }
} persons[MX_N];
ll sum[MX_N], n, dp[MX_N][MX_N * MX_N];
int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &persons[i].a, &persons[i].b);
    sort(persons + 1, persons + 1 + n);
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + persons[i].a;
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= sum[i]; j++)
        {
            if (j >= persons[i].a)
                dp[i][j] = min(dp[i][j], max(dp[i - 1][j - persons[i].a], (ll)(j + persons[i].b)));
            dp[i][j] = min(dp[i][j], max(dp[i - 1][j], sum[i] - j + persons[i].b));
        }
    ll ans = 0x7fffffff;
    for (int i = 0; i <= sum[n]; i++)
        ans = min(ans, dp[n][i]);
    printf("%lld", ans);
    return 0;
}

用单调队列优化动态规划

Introduction

有的时候我们在日常写题时，会碰见这样的毒瘤 DP 题目，他们一般有以下特性：

  • 多维度动态规划
  • 循环层数很多，在极限数据下无法 AC。
  • 一般出现在区间 DP 中，一般暴力算法复杂度为\(O(n^3)\)。

这个时候我们可以使用单调队列来优化，时间复杂度可以进一步降至\(O(n^2)\)或者是\(O(nm)\)。如果有不会单调队列的同学呢可以去学习以下，顺便可以看看这篇文章：CH1201:最大子序和题解

Overall on this optimization technique

我们来看一道例题：Fence – POJ这道题是一道比较简单的经典 DP。设计状态\(dp[i][j]\)表示前\(i\)个人搞定了前\(j\)个单位的墙。写出方程式：

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]+profit_i*(j-k)\}\]

这样的话，整个算法的复杂度是\(O(n^3)\)的。我们能不能将其降为\(O(n^2)\)呢？我们可以把整个方程变个形，之后方程是这样的：

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]-profit_i*k\}+profit_i*j\]

我们发现，这样的话整个方程在\(i\)的循环之下，算是只跟变量\(k\)扯上关系了。我们会发现，只要有\(k_1<k_2\)且\(dp[i-1][k_1]-profit_i*k_1<dp[i-1][k_2]-profit_i*k_2\)，那么就可以直接排除掉答案\(k_1\)。那么就可以使用单调队列来做到这一点。

下面是核心的 DP 代码：

int calc(int i, int k)
{
    return dp[i - 1][k] - wks[i].p * k;
}

// in ( int main() )
for (int i = 1; i <= k; i++)
{
    deque<int> q;
    for (int j = max(0, wks[i].s - wks[i].l); j <= wks[i].s - 1; j++)
    {
        while (!q.empty() && calc(i, q.back()) <= calc(i, j))
            q.pop_back();
        q.push_back(j);
    }
    for (int j = 1; j <= n; j++)
    {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        if (j >= wks[i].s)
        {
            while (!q.empty() && q.front() < j - wks[i].l)
                q.pop_front();
            if (!q.empty())
                dp[i][j] = max(dp[i][j], calc(i, q.front()) + wks[i].p * j);
        }
    }
}

In Conclusion

整个单调队列优化会为后面的斜率优化做基础（因为我学这个单调队列优化就是有一道题要求使用斜率优化），所以请务必搞懂这个操作。

Codeforces 2B:The least round way 题解

主要思路

这道题我一开始写的是纯暴力，然后卡在了第 6 个点上失败。在看题解之前就已经感觉到这应该跟数学有关系。我先大概地说明主要方法，在数字输入时用数组\(dp2[][]和dp5[][]\)来记录这个数字包含因子\(2\)的个数和因子\(5\)的个数，然后尾部\(0\)的个数是\(min\{numOf(2),numOf(5)\}\)。然后我们可以分开进行处理，可以先处理\(dp2[][]\)数组并记录路径数组\(f2[][]\)，之后处理\(dp2[][]和f5[][]\)。统计答案时只需要比较\(dp2[n][n]和dp5[n][n]\)，回溯\(f2[][]或f5[][]\)即可。

但是还有一种情况，那就是数字矩阵包括\(0\)的情况。我们可以考虑在预处理的时候记录下数字\(0\)的坐标，最后只要\(min\{dp2[n][n],dp5[n][n]\}>1\)，就证明\(0\)才是最优解。

代码

// CF2B.cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const int MX_N = 1010;
ll mat[MX_N][MX_N], dp2[MX_N][MX_N], dp5[MX_N][MX_N], pow2[25], pow5[25], n, zeroFlag, zeroX, zeroY;
char ans[MX_N << 1];
struct vec
{
    ll x, y;
} f2[MX_N][MX_N], f5[MX_N][MX_N];
void preprocess()
{
    for (int i = 0; i < 25; i++)
        pow2[i] = 1 << i;
    pow5[0] = 1;
    for (int i = 1; i < 25; i++)
        pow5[i] = pow5[i - 1] * 5;
}
void processDp()
{
    // start to program dynamically;
    for (int i = 2; i <= n; i++)
        dp2[0][i] = dp2[i][0] = dp5[0][i] = dp5[i][0] = 2e9;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            ll vald = dp2[i - 1][j], valr = dp2[i][j - 1];
            dp2[i][j] += min(vald, valr);
            if (vald < valr)
                f2[i][j] = vec{i - 1, j};
            else
                f2[i][j] = vec{i, j - 1};
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            ll vald = dp5[i - 1][j], valr = dp5[i][j - 1];
            dp5[i][j] += min(vald, valr);
            if (vald < valr)
                f5[i][j] = vec{i - 1, j};
            else
                f5[i][j] = vec{i, j - 1};
        }
}
int main()
{
    scanf("%lld", &n);
    preprocess();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            scanf("%lld", &mat[i][j]);
            if (mat[i][j] == 0)
            {
                zeroFlag = true, zeroX = i, zeroY = j;
                continue;
            }
            int tmp = mat[i][j];
            for (int k = 24; k >= 0; k--)
                if (tmp % pow2[k] == 0)
                    dp2[i][j] += k, tmp /= pow2[k];
            if (tmp % 2 == 0)
                dp2[i][j]++;
            tmp = mat[i][j];
            for (int k = 24; k >= 0; k--)
                if (tmp % pow5[k] == 0)
                    dp5[i][j] += k, tmp /= pow5[k];
            if (tmp % 5 == 0)
                dp2[i][j]++;
        }
    processDp();
    // process the answer;
    if (zeroFlag && min(dp2[n][n], dp5[n][n]) > 1)
    {
        puts("1");
        for (int i = 2; i <= zeroX; i++)
            putchar('D');
        for (int j = 2; j <= zeroY; j++)
            putchar('R');
        for (int i = zeroX + 1; i <= n; i++)
            putchar('D');
        for (int j = zeroY + 1; j <= n; j++)
            putchar('R');
        return 0;
    }
    // secondary answer;
    printf("%d\n", min(dp2[n][n], dp5[n][n]));
    int cx = n, cy = n, tot = 0;
    for (int counter = 1; counter <= 2 * n - 1; counter++)
    {
        int fx = f2[cx][cy].x, fy = f2[cx][cy].y;
        if (dp2[n][n] > dp5[n][n])
            fx = f5[cx][cy].x, fy = f5[cx][cy].y;
        if (cx > fx)
            ans[counter] = 'D';
        else
            ans[counter] = 'R';
        cx = fx, cy = fy;
    }
    for (int i = 2 * n - 2; i >= 1; i--)
        printf("%c", ans[i]);
    return 0;
}

CH5105:Cookies 题解

主要思路

显然，这是一道动态规划的题目。这道线性 DP 的方程极其难推，因为在正常推的情况下，总要考虑状态前的状态才能进行 DP。然而，这道题有一个思路清奇的方法。

首先是预处理部分：我们需要把孩子的愤怒值按升序排列，并且记录每一个孩子前后的序号映射。

bool compare(const ll &a, const ll &b)
{ 
    return g[a] > g[b]; 
}

scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
    scanf("%lld", &g[i]), c[i] = i;
sort(c + 1, c + n + 1, compare);

状态表示很容易想出，\(dp[i][j]\)代表给前\(i\)个人分配了\(j\)块饼干。不过 DP 的过程非常的神奇，考虑两个分支

  • 其一就是把前\(i\)个人的饼干都取走一个，加在第\(i\)个小孩身上，这样的话前面的愤怒值其实相对来讲是不变的，可直接转移\(dp[i][j] = dp[i][j-i]\)。
  • 之后我们再来考虑把中间的段分开来考虑取走的问题。我们可以枚举一个端点\(k \in [0,i)\)，然后我们可以设区间\([1,k]\)不动，从区间\([k+1,i]\)中取走若干个曲奇。这样的话应该这样转移：\(dp[i][j] = min\{ dp[k][j-(i-k)]+k*\sum^{i}_{p=k+1}g[p]\}\)。我们可以写成前缀和形式：\(dp[i][j] = min\{ dp[k][j-(i-k)]+k*(sum[i]-sum[k])\}\)。

这样我们就搞定了 DP 部分。我们还需要统计饼干数量，可以考虑在转移过程中记录一些信息来搞定尾处理。

代码

// CH5105.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int MX_N = 35, MX_M = 5100;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m, g[MX_N], dp[MX_N][MX_M], c[MX_N], presum[MX_N];
ll lastPersonNum[MX_N][MX_M], cookieSum[MX_N][MX_M], ans[MX_N];
bool compare(const ll &a, const ll &b) { return g[a] > g[b]; }
void process(int num, int bis)
{
    if (num == 0)
        return;
    process(lastPersonNum[num][bis], cookieSum[num][bis]);
    if (lastPersonNum[num][bis] == num)
        for (int i = 1; i <= num; i++)
            ans[c[i]]++;
    else
        for (int i = lastPersonNum[num][bis] + 1; i <= num; i++)
            ans[c[i]] = 1;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &g[i]), c[i] = i;
    sort(c + 1, c + n + 1, compare);
    for (int i = 1; i <= n; i++)
        presum[i] = presum[i - 1] + g[c[i]];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int bis = i; bis <= m; bis++)
        {
            dp[i][bis] = dp[i][bis - i];
            lastPersonNum[i][bis] = i;
            cookieSum[i][bis] = bis - i;
            for (int k = 0; k < i; k++)
            {
                ll val = dp[k][bis - (i - k)] + k * (presum[i] - presum[k]);
                if (dp[i][bis] > val)
                    dp[i][bis] = val, lastPersonNum[i][bis] = k, cookieSum[i][bis] = bis - (i - k);
            }
        }
    printf("%lld\n", dp[n][m]);
    process(n, m);
    for (int i = 1; i <= n; i++)
        printf("%lld ", ans[i]);
    return 0;
}

P2831:愤怒的小鸟题解

思路

这一题是一道状压 DP（见数据范围）。我们把猪的死活压缩起来作为状态，整个程序从\(0\)开始计数，可以推出以下几个方程：\(f[stat|(1<<i)] = min(f[stat|(1<<i)], f[stat] + 1)\)和\(f[stat|dotset[i][j]] = min(f[stat|dotset[i][j]],f[stat]+1)\)，其中dotset为经过点\(i,j\)的抛物线的点集。这个算法是\(O(Tn^2 2^n)\)，不够优秀。我们可以使用一个方法把\(n^2\)化为\(n\)。我们可以预先处理出每一个状态下第一个健在猪的编号，然后我们只要转移这一只猪即可，因为未来的猪都会被处理，所以可以直接降维。

代码

// P2831.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define pr pair<double, double>
using namespace std;
const double eps = 1e-8;
int T, n, dotset[19][19], dp[(1 << 19)], lbit[(1 << 19)], m;
pr prs[20];
void solve(double &x, double &y, double a1, double b1, double c1, double a2, double b2, double c2)
{
    y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
    x = (c1 - b1 * y) / a1;
}
int main()
{
    for (int i = 0; i < (1 << 18); i++)
    {
        int bit = 0;
        for (; bit < 18 && (i & (1 << bit)) ; bit++)
            ;
        lbit[i] = bit;
    }
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        memset(dp, 0x3f, sizeof(dp)), memset(dotset, 0, sizeof(dotset));
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &prs[i].first, &prs[i].second);
        // process the curves;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (fabs(prs[i].first - prs[j].first) < eps)
                    continue;
                double a, b;
                solve(a, b, prs[i].first * prs[i].first, prs[i].first, prs[i].second,
                      prs[j].first * prs[j].first, prs[j].first, prs[j].second);
                if (a > -eps)
                    continue;
                for (int k = 0; k < n; k++)
                    if (fabs(a * prs[k].first * prs[k].first + b * prs[k].first - prs[k].second) < eps)
                        dotset[i][j] |= (1 << k);
            }
        dp[0] = 0;
        for (int stat = 0; stat < (1 << n); stat++)
        {
            int esspt = lbit[stat];
            dp[stat | (1 << esspt)] = min(dp[stat | (1 << esspt)], dp[stat] + 1);
            for (int k = 0; k < n; k++)
                dp[stat | dotset[esspt][k]] = min(dp[stat | dotset[esspt][k]], dp[stat] + 1);
        }
        printf("%d\n", dp[(1 << n) - 1]);
    }
    return 0;
}

P2051:「AHOI2009」中国象棋题解

这是一道比较优秀的方案数 DP 题。乍一看以为是状压 DP，然后发现数据范围过大所以只能重新思考（也就是看题解）。我们可以写出状态格式：

\[dp[ln][opit][tpit]，其中 ln 为行号，opit 代表第 ln 行内一个棋子的列数，tpit 代表第 ln 行内两个棋子的列数。\]

然后我们就可以根据不同情况来进行转移了。我们来看下面几组代码，其中每组都会有对应方程的意义。我们记\(dp[ln+1]\)为当前行号。首先，我们先要判定转移源的方案数不为\(0\)，之后再进行转移。

// 不放置棋子的情况;
// Situation without placing;
dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
// 在不放置棋子的位置上放置一个棋子;
// Situation of placing one on empty lines;
if (M - opit - tpit >= 1)
    dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
// 在放置了一个棋子的位置上放置一个棋子；
// Situation of placing one on lines with only piece;
if (opit >= 1)
    dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
// 在两个没有放置棋子的位置上放置两个棋子，其中 C2(num) = C^num_2;
// Situation of placing two pieces on the two empty slots;
if (M - opit - tpit >= 2)
    dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
// 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
// Situation of placing one on the empty and another on the only slot;
if (M - opit - tpit >= 1 && opit >= 1)
    dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
// 在两个一个棋子的位置放置共两个棋子;
// Situation of placing two on two only slots;
if (opit >= 2)
    dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;

完整源码：

// P2051.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int MX_N = 102, MOD = 9999973;
ll dp[MX_N][MX_N][MX_N], N, M;
ll C2(ll num)
{
    return (num * (num - 1)) / 2;
}
int main()
{
    scanf("%lld%lld", &N, &M);
    dp[0][0][0] = 1;
    for (int ln = 0; ln < N; ln++)
        for (int opit = 0; opit <= M; opit++)
            for (int tpit = 0; tpit + opit <= M; tpit++)
                if (dp[ln][opit][tpit])
                {
                    // 不放置棋子的情况;
                    // Situation without placing;
                    dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
                    // 在不放置棋子的位置上放置一个棋子;
                    // Situation of placing one on empty lines;
                    if (M - opit - tpit >= 1)
                        dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
                    // 在放置了一个棋子的位置上放置一个棋子；
                    // Situation of placing one on lines with only piece;
                    if (opit >= 1)
                        dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
                    // 在两个没有放置棋子的位置上放置两个棋子，其中 C2(num) = C^num_2;
                    // Situation of placing two pieces on the two empty slots;
                    if (M - opit - tpit >= 2)
                        dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
                    // 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
                    // Situation of placing one on the empty and another on the only slot;
                    if (M - opit - tpit >= 1 && opit >= 1)
                        dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
                    // 在两个一个棋子的位置放置共两个棋子;
                    // Situation of placing two on two only slots;
                    if (opit >= 2)
                        dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;
                }
    ll ans = 0;
    for (int i = 0; i <= M; i++)
        for (int j = 0; i + j <= M; j++)
            ans = (ans + dp[N][i][j]) % MOD;
    printf("%lld\n", ans);
    return 0;
}