区间DP
前言
狂补DP QAQ
Optimal Binary Search Tree - UVA - 10304
题意
最优二分搜索树问题
思路
定义DP状态，dp[i][j]表示区间[i,j]构成的子树的权值和最小值，那么dp[i][j] = min{dp[i][k - 1] + sum(i, k - 1) + dp[k + 1][j] + sum(k + 1, j)}，即现在选择k为根，那么当前的权值和就是左右子树的权值和，但是由于左右子树深度全部下降了1，因此要加上sum，补上这部分的权值
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 250 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N], dp[N][N], sum[N];
void solve(int n){
for(int i = n; i >= 1; i--){
for(int j = i; j <= n; j++){
dp[i][j] = (i == j ? 0 : inf);
for(int k = i; k <= j; k++){
int ret = 0;
if(i <= k - 1 && k - 1 >= 1) ret += (dp[i][k - 1] + sum[k - 1] - sum[i - 1]);
if(k + 1 <= j && k + 1 <= n) ret += (dp[k + 1][j] + sum[j] - sum[k]);
dp[i][j] = min(dp[i][j], ret);
}
}
}
}
int main(){
int n;
while(~scanf("%d", &n)){
sum[0] = 0;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
solve(n);
printf("%d\n", dp[1][n]);
}
}
Recovering BST - CodeForces - 1025D
题意
给定一个升序序列，问题能否构造出一棵二分搜索树，使其每条边上的两点都满足不互质
思路
如果和上题一样，定义dp[i][j]为能否构成这样一棵子树，那么显然dp[i][j]可以从dp[i][k - 1]和dp[k + 1][j]转移而来，但是我们此时需要多加一个信息即谁为根，也就是定义为dp[i][j][k]为以k为根，区间[l,r]构造的树能否成立，但是完成这个算法就需要O(n^4)的时间，显然是不可取的
因此需要换一种定义状态的方式，定义dp[i][j][0]为区间[i,j]组成的树可以为根j+1的左子树，dp[i][j][1]为区间[i,j]组成的树为根i-1的右子树，那么
dp[i][j][0] |= dp[i][k - 1][0] & dp[k + 1][j][1] & (gcd(a[k], a[j + 1] > 1))
dp[i][j][1] |= dp[i][k - 1][0] & dp[k + 1][j][1] & (gcd(a[k], a[i - 1] > 1))
画图可知以上二式
最后的答案就再枚举一遍k，能使得dp[1][k - 1][0] & dp[k + 1][n]为1，则为Yes，否则为No
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 700 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N], dp[N][N][2];
bool ok[N][N];
void init(int n){
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
ok[i][j] = ok[j][i] = (__gcd(a[i], a[j]) > 1);
}
}
}
bool solve(int n){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++){
if(i + 1 <= n) dp[i][i][0] = ok[i][i + 1];
if(i - 1 >= 1) dp[i][i][1] = ok[i][i - 1];
}
for(int i = n; i >= 1; i--){
for(int j = i; j <= n; j++){
if(i == j) continue;
for(int k = i; k <= j; k++){
int t1 = 1, t2 = 1;
if(i <= k - 1 && k - 1 >= 1){
t1 &= dp[i][k - 1][0];
t2 &= dp[i][k - 1][0];
}
if(k + 1 <= j && k + 1 <= n){
t1 &= dp[k + 1][j][1];
t2 &= dp[k + 1][j][1];
}
t1 &= ok[k][j + 1];
t2 &= ok[k][i - 1];
dp[i][j][0] |= t1;
dp[i][j][1] |= t2;
}
}
}
for(int k = 1; k <= n; k++){
if(k == 1 && dp[k + 1][n][1]) return true;
if(k == n && dp[1][k - 1][0]) return true;
if(dp[k + 1][n][1] && dp[1][k - 1][0]) return true;
}
return false;
}
int main(){
int n;
while(~scanf("%d", &n)){
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
init(n);
puts(solve(n) ? "Yes" : "No");
}
}
Lighting System Design - UVA - 11400
题意
给定n种灯泡，每种灯泡由电压值V，电源费用K，单个费用C和数量L，不同种类的灯泡必须用不同的电源，同一种则可以用相同的电源，现在可以将一些灯泡换成电压更高的另一些灯泡，问最小费用
思路
首先可以肯定的是，对于一种灯泡，要么全换，要么不换，毕竟只换一半还要多一个电源的钱，不划算的
然后按照电压值从小到大排序，那么第二件可以肯定的是，对于某一个灯泡，换成它的灯泡必定是以他为终点的一段连续子区间
举个栗子，假如由1 2两种灯泡，1没有换成2，这时候加入一个电压更高的灯泡3，那么假如1换成3更划算，又因为1没有换成2，说明1换成2是不划算的，那么2换成3当然会更划算，所以1和2就得全部换成3，如果1换成3不划算，那么2可能换成3，也可能不换成3，但都是一个连续子区间
定义DP状态dp[i]代表排序后到第i个灯泡时所花的费用最小值，那么dp[i] = min(dp[i], dp[k] + (sum[i] - sum[k])*a[i].c + a[i].k)，其中sum是数量的前缀和
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 1000 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct Light{
int v, k, c, l;
bool operator < (const Light& b) const{
return v < b.v;
}
};
Light a[N];
ll dp[N], sum[N];
int main(){
int n;
while(~scanf("%d", &n) && n){
memset(dp, 0x3f, sizeof(dp));
sum[0] = 0, dp[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%d%d%d%d", &a[i].v, &a[i].k, &a[i].c, &a[i].l);
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++){
sum[i] = sum[i - 1] + a[i].l;
}
for(int i = 1; i <= n; i++){
for(int k = 0; k <= i - 1; k++){
dp[i] = min(dp[i], dp[k] + (sum[i] - sum[k])*a[i].c + a[i].k);
}
}
printf("%lld\n", dp[n]);
}
}
Multiplication Puzzle - POJ - 1651
题意
最优矩阵链乘问题
思路
定义DP状态dp[i][j]代表区间[i,j]链乘的最小值，那么dp[i][j] = min{dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]}
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 100 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
ll dp[N][N], a[N];
int main(){
int n;
while(~scanf("%d", &n)){
memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i <= n; i++){
dp[i][i] = dp[i][i + 1] = 0;
scanf("%lld", &a[i]);
}
for(int i = n; i >= 1; i--){
for(int j = i; j <= n; j++){
for(int k = i; k <= j; k++){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]);
}
}
}
printf("%lld\n", dp[1][n]);
}
}
Brackets sequence - UVA - 1626
题意
括号序列匹配问题，要求添加最少括号使得给定的字符串括号匹配，并且要求输出该字符串
思路
定义DP状态dp[i][j]代表区间[i,j]括号匹配的最大值，那么
dp[i][j] = max{dp[i + 1][j - 1] + 1}
dp[i][j] = max{dp[i][k] + dp[k + 1][j]}
最难的地方应该是如何输出，按照紫书的写法，只需要最后根据dp[i][j]的计算结果递归输出即可
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 100 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
char s[N];
int dp[N][N];
bool isMatch(int i, int j){
if(s[i] == '(' && s[j] == ')') return true;
if(s[i] == '[' && s[j] == ']') return true;
return false;
}
void mgets(char* s){
while((* s = getchar()) != '\n') s++;
* s = 0;
}
void print(int i, int j){
if(i > j) return;
if(i == j){
printf(s[i] == '(' || s[i] == ')' ? "()" : "[]");
return;
}
if(isMatch(i, j) && dp[i][j] == dp[i + 1][j - 1] + 1){
putchar(s[i]);
print(i + 1, j - 1);
putchar(s[j]);
return;
}
for(int k = i; k + 1 <= j; k++){
if(dp[i][j] != dp[i][k] + dp[k + 1][j]) continue;
print(i, k);
print(k + 1, j);
return;
}
}
int main(){
int t;
scanf("%d", &t);
getchar();
while(t--){
memset(dp, 0, sizeof(dp));
mgets(s + 1);
mgets(s + 1);
int n = strlen(s + 1);
for(int i = n; i >= 1; i--){
for(int j = i + 1; j <= n; j++){
if(isMatch(i, j)) dp[i][j] = dp[i + 1][j - 1] + 1;
for(int k = i; k + 1 <= j; k++){
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
print(1, n);
puts("");
if(t > 0) puts("");
}
}
Partitioning by Palindromes - UVA - 11584
题意
给定字符串，要求划分出最少的回文子串区间
思路
首先定义一个DP状态ok[i][j]用来记录子串[i,j]是否为回文串，则
ok[i][j] = true, i == j || i + 1 == j && s[i] == s[j]
ok[i][j] = false, s[i] != s[j]
ok[i][j] = ok[i + 1][j - 1]
再定义一个DP状态dp[i]代表到第i个字符时所能划分出的最少回文子串区间数，则dp[i] = min{dp[k] + 1, k < i && ok[k + 1][i]}
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 1000 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
char s[N];
int dp[N];
bool ok[N][N];
void initPalindrome(int n){
for(int i = n; i >= 1; i--){
for(int j = i; j <= n; j++){
if(i == j) ok[i][j] = true;
else if(s[i] != s[j]) ok[i][j] = false;
else if(i == j || i + 1 == j) ok[i][j] = true;
else ok[i][j] = ok[i + 1][j - 1];
}
}
}
int solve(int n){
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int k = 0; k <= i - 1; k++){
if(ok[k + 1][i]) dp[i] = min(dp[i], dp[k] + 1);
}
}
return dp[n];
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%s", s + 1);
int n = strlen(s + 1);
initPalindrome(n);
printf("%d\n", solve(n));
}
}
Color Length - UVA - 1625
题意
有两个序列，每次可以将其中一个序列的头部字符取走放入一个新序列中，定义价值为新序列中每个字符最开始出现的位置和最后出现的位置的距离之差的和，求价值最小值
思路
首先预处理出每个字母在序列中第一次和最后一次出现的位置，然后定义DP状态sum[i][j]代表在第一个字符串到i，第二个字符串到j时，出现但未结束的字母个数，再处理完sum[i][j]（如何处理见代码，试出来的 T^T）
然后定义DP状态dp[i][j]为第一个字符串到i，第二个字符串到j时的价值最小值，则dp[i][j] = min{dp[i - 1][j], dp[i][j - 1] + sum[i][j]}
因为根据DP方程来DP的话，初态处理比较麻烦，所以下面代码做了个变形
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 5000 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
char s[N], p[N];
int startpos[2][128], endpos[2][128];
int sum[N][N], dp[N][N];
inline void init(int n, int m){
for(int i = 0; i <= n + 1; i++){
for(int j = 0; j <= m + 1; j++){
dp[i][j] = inf;
sum[i][j] = 0;
}
}
memset(startpos, 0x3f, sizeof(startpos));
memset(endpos, 0, sizeof(endpos));
dp[0][0] = 0;
}
void getSum(int n, int m){
for(char ch = 'A'; ch <= 'Z'; ch++){
for(int i = 1; i <= n; i++){
if(s[i] != ch) continue;
startpos[0][ch] = i;
break;
}
for(int i = n; i >= 1; i--){
if(s[i] != ch) continue;
endpos[0][ch] = i;
break;
}
for(int i = 1; i <= m; i++){
if(p[i] != ch) continue;
startpos[1][ch] = i;
break;
}
for(int i = m; i >= 1; i--){
if(p[i] != ch) continue;
endpos[1][ch] = i;
break;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
sum[i + 1][j] = sum[i][j + 1] = sum[i][j];
char& ch1 = s[i + 1];
char& ch2 = p[j + 1];
if(i + 1 == startpos[0][ch1] && j < startpos[1][ch1]) sum[i + 1][j]++;
if(i + 1 == endpos[0][ch1] && j >= endpos[1][ch1]) sum[i + 1][j]--;
if(j + 1 == startpos[1][ch2] && i < startpos[0][ch2]) sum[i][j + 1]++;
if(j + 1 == endpos[1][ch2] && i >= endpos[0][ch2]) sum[i][j + 1]--;
}
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%s%s", s + 1, p + 1);
int n = strlen(s + 1), m = strlen(p + 1);
init(n, m);
getSum(n, m);
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + sum[i + 1][j]);
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + sum[i][j + 1]);
}
}
printf("%d\n", dp[n][m]);
}
}
