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