区间DP

POJ 1991 Turning in Homework

Posted on

/doge薛昊老是偷我题做,最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有,这个区间DP的套路我还真没碰到过。

这是一个大区间推小区间的套路。

题意:
小明要在某层楼的各个老师那里交一大堆作业,但是小明来早了,老师还没上班,他站在这层楼的最左边,告诉你每个老师的上班时间,最后要在某个给定位置下楼,问最少时间。

思路:
shit,完全是看博客,看代码敲的。
一个比较困难的点在于给定离开地点,算了,不装了,就算取消这个条件我也写不来……
明确可以用dp求解,首先按照位置优先开门顺序次优的顺序排序,设三维数组 $dp[l][r][k]$。
当 $k=0$ 时,表示只有 $(l,r] $ 区间内的作业没有交。
而 $k=1$ 时,表示只有 $[l,r) $ 区间内的作业没有交。
而我们的其实状态$dp[1][n][0/1]$是已知的,我们完全可以由此不断向内挤压求出小区间的结果。
当 $l=r$ 时,则所有作业交完,且停在 $l$ 点。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int dp[maxn][maxn][2];
pii point[maxn];

int getDis(int d, int s) { return point[d].first - point[s].first; }

int main()
{
    int n, h, b;
    scanf("%d %d %d", &n, &h, &b);
    range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
    sort(point + 1, point + 1 + n);
    fill(dp, 0x3f);
    dp[1][n][0] = max(point[1].first, point[1].second);
    dp[1][n][1] = max(point[n].first, point[n].second);
    rrange(len, 1, n - 1) range(l, 1, n + 1 - len)
    {
        int r = l + len - 1;
        if (l > 1) {
            dp[l][r][0] = min(dp[l][r][0], dp[l - 1][r][0] + getDis(l, l - 1));
            dp[l][r][1] = min(dp[l][r][1], dp[l - 1][r][0] + getDis(r, l - 1));
        }
        if (r < n) {
            dp[l][r][0] = min(dp[l][r][0], dp[l][r + 1][1] + getDis(r + 1, l));
            dp[l][r][1] = min(dp[l][r][1], dp[l][r + 1][1] + getDis(r + 1, r));
        }
        dp[l][r][0] = max(dp[l][r][0], point[l].second);
        dp[l][r][1] = max(dp[l][r][1], point[r].second);
    }
    int ans = inf;
    range(i,1,n) ans = min(ans,dp[i][i][0]+abs(b-point[i].first));
    printf("%d\n",ans);
    return 0;
}
区间DP

区间DP入门 —— 三类经典问题

Posted on

例行废话

大概是前天试着去入门区间DP,中间穿插了很多其他题目,今天勉强入门并多写了几题。

又被goubi带鱼笑了,shit!
有些时候我自己也会觉得写一些入门的东西会有点浪费时间……
但我又想了想,应该说是每个人写博文的目的不同吧。
像我这种小网站,我也不渴求能帮到多少人,只是记录一下自己的成长罢了。

三类经典问题

区间DP被goubi带鱼说是最简单的DP,因为它是有套路可循的。
这个套路就是用小区间推出大区间。是的,这个套路就是这么简单,其他的还是考虑状态与个人思维了。
而小区间推出大区间的方法自然是按照区间长度不断向后DP,每次将所有长度相同的区间长度推出。
一般来说,把这个这个思维熟练了,再学一个四边形优化,区间DP就可以毕业了。goubi带鱼如是说

而关于三类经典问题,大多数区间DP都可以通过转换得到这三类基础模型。当然我也是听别人说啦,我也才刚入门啊

石子归并

传送门

题意:

给你一排石子,你只能将相邻的石子合成一堆,花费为两堆石子的重量和。问如何合并,花费最小。

思路:

如果去掉相邻石子才能合并的限制,那就是一个裸的哈夫曼树。
而考虑这个限制的话,就得用区间DP的思想了。

一开始我觉得,裸题,直接区间值不断相加就好了。事实上不行,我并没有考虑好区间所表示的含义。
每个区间就是每个状态,状态的意义在DP中的位置非常重要。

每个区间的确是合并所得区间的最小花费,但是还需要考虑一个合并花费,而合并花费其实就是这个区间的石子总数。因此,问题得到了解决。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const int maxn = 205;
int dp[maxn][maxn];
int ary[maxn], sum[maxn];

int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        fill(dp, 0), fill(sum, 0);
        range(i, 1, n) scanf("%d", ary + i), sum[i] = sum[i - 1] + ary[i];
        range(len, 2, n)
        {
            for (int l = 1, r = len; r <= n; l++, r++) {
                dp[l][r] = inf;
                range(i, l, r - 1) dp[l][r] = min(dp[l][r], dp[l][i] + dp[i+1][r] + sum[r] - sum[l-1]);
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}

括号匹配

传送门

题意:

给你一个括号序列,要你找出,最长的满足两两匹配的子序列。

思路:

这个较为简单,基本思路是找出可以扩展的状态,之后就是区间合并找最小了。

这里可扩展的状态为 左右两边是否能组成成型的括号,如果能,则 \( dp[ l ] [ r ] = dp [ l + 1 ] [ r - 1] + 2 \) ,否则, \( dp [ l ] [ r ] = dp [ l + 1 ] [ r - 1 ] \)。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int maxn = 105;
int dp[maxn][maxn];

char str[maxn];

int main()
{
    int len;
    while (scanf("%s", str) != EOF && strcmp(str, "end") != 0) {
        len = strlen(str), fill(dp, 0);
        each(i, len)
        {
            for (int l = 0, r = i; r < len; l++, r++) {
                if ((str[l] == '(' && str[r] == ')') || (str[l] == '[' && str[r] == ']'))
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                range(k, l + 1, r - 1) dp[l][r] = max(dp[l][k] + dp[k][r], dp[l][r]);
            }
        }
        printf("%d\n", dp[0][len - 1]);
    }
    return 0;
}

整数划分

传送门

题意:

给你一个整数 n ,要你从中间插入 m - 1 个乘号,使得所得结果最大。

思路:

套路基本是一致的,只不过这里的区间是乘号的数量。
\( dp[len][num] \) 表示从 \( [ 0, len ] \) 中放 \( num\) 个乘好对应的最大值。
转移方程如下:
$ dp [ i ] [ j ] = \max (dp [ i ] [ j ] , dp [ k ] [ j-1 ] * a [ k+1 ] [ i ] ) $

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const int maxn = 25;

int m;
char num[maxn];
ll dp[maxn][maxn], a[maxn][maxn];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        fill(dp, 0);
        scanf("%s %d", num, &m);
        int len = strlen(num);
        each(i, len) a[i][i] = num[i] - '0';
        range(i, 1, len - 1) for (int l = 0, r = i; r < len; l++, r++) {
            a[l][r] = a[l][r - 1] * 10 + num[r] - '0';
        }
        each(i, len) dp[i][1] = a[0][i];
        range(l, 2, m) range(i, l-1, len - 1)
        {
            each(pos, i) dp[i][l] = max(dp[i][l], dp[pos][l - 1] * a[pos + 1][i]);
        }
        printf("%lld\n", dp[len - 1][m]);
    }
    return 0;
}