例行废话

大概是前天试着去入门区间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;
}