Multiplication Puzzle—区间DP

题意:有排成一行的卡片,每次取一张卡片(不能取开头和结尾的卡片)并获得一个值:该卡片上的数字和它相邻的两张卡片的数字乘积。重复上述操作直到最终只剩下两张卡片,求将得到的所有值加起来最小可以是多少

思路:考虑用 dp[i][j] 表示从第 i 张卡片到第 j 张卡片中抽卡直到剩余两张能得到的最小值,那么可以枚举区间最后一张抽取的卡牌为 k,状态转移方程得 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]),满足 i<j<k

初始化就是区间长度为 1 和 2 的区间无疑都是 0,从区间长度为 3 的计算开始,最终答案就是 dp[1][n]

递推写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//假设dp[i][j]表示将(i,j)内的卡牌那空的最小值,枚举k
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
using namespace std;
typedef long long ll;

int a[105];
int dp[105][105];

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
memset(dp, 0x3f, sizeof dp);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
dp[i][i] = 0; //边界
dp[i][i+1]=0;
}
for (int l = 3; l <= n; ++l) { //从长度为3的区间开始计算
for (int i = 1; i + l <= n + 1; ++i) {
int j = i + l - 1;
for (int k = i + 1; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
}
}
cout << dp[1][n] << endl;
//system("pause");
return 0;
}

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//假设dp[i][j]表示将(i,j)内的卡牌那空的最小值,枚举k
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
using namespace std;
typedef long long ll;

int a[105];
int dp[105][105];

int func(int l,int r){
if(dp[l][r]!=0x3f3f3f3f)return dp[l][r];
for(int k=l+1;k<r;++k)
dp[l][r]=min(dp[l][r],func(l,k)+func(k,r)+a[l]*a[k]*a[r]);
return dp[l][r];
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
memset(dp, 0x3f, sizeof dp);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
dp[i][i] = 0; //边界
dp[i][i+1]=0;
}
cout <<func(1,n) << endl;
//system("pause");
return 0;
}

Brackets—区间DP

题意:输入一个字符串,只包括 [ ] ( ) 这四种字符,求合法(序列中两种类型的括号都有对应的组合并且不交叉)最长合法括号子序列的长度

1
2
3
4
((()))  //合法
()()() //合法
([][]) //合法
([)] //不合法

思路:考虑用 dp[i][j] 表示以第 i 到第 j 个字符组成的合法子序列的最大长度,那么分为两种转移方式:

  • 第 i 个字符和第 j 个字符对应组合:dp[i][j]=dp[i+1][j-1]+2
  • 否则的话就是分为包含 i 和 j 字符的两部分,枚举分开的位置并加和每个部分取最长:dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]) 满足 i<k<j

初始化 dp 数组为 0 为了取最大值同时如果取到未知区间也返还 0,最终答案就是 dp[1][len]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[105][105];

int main() {
char s[105];
while (scanf("%s", s + 1) != EOF) {
memset(dp, 0, sizeof(dp)); //dp初始化为0,因为一方面是找最大之,一方面初始匹配数为0
int len = strlen(s + 1); //dp[i][i]不用处理,因为自己和自己不匹配就是0
if (s[1] == 'e') break;
for (int l = 1; l <= len; l++) {
for (int i = 1; i + l <= len + 1; i++) {
int j = i + l - 1;
if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')) { //如果匹配,先更新
dp[i][j] = dp[i + 1][j - 1] + 2;
}
for (int k = i; k < j; k++) { //k<j
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
cout << dp[1][len] << endl;
}
return 0;
}

Palindrome subsequence—区间DP

题意:定义子序列可以是序列中一些不连续的字符组成,请找出给出的序列中最大有多少种回文子序列的组合数量,答案对 1e4+7 取模

思路:考虑用 dp[i][j] 表示第 i 到 j 字符的回文子序列的组合数量

  • 先不考虑第 i 和 第 j 个字符是否相同,那么 dp[i][j]=(dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+mod)%mod,即区间 [i+1,j-1] 的字符和两个新的字符分别组合多出来的组合数量,中间多算了一次 dp[i+1][j-1] 所以减去一次重叠部分。
  • 再考虑如果第 i 和第 j 个字符相同的话,那么 dp[i][j] 在上述基础上还可以进一步更新 dp[i][j]=(dp[i][j]+dp[i +1][j-1]+1)%mod,即用区间 [i+1,j-1] 的字符和两个新的字符共同组合多出来的组合数量

初始化区间长度为 1的序列本身就是回文的所以 dp[i][i]=1,最终答案就是 dp[1][len]

递推写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//dp[i][j]表示[i,j]内的最大回文子串的数量
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int mod = 1e4 + 7;

int dp[1005][1005];

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
for (int _ = 1; _ <= t; ++_) {
char s[1005];
scanf("%s", (s + 1));
cout << "Case " << _ << ": ";
int len = strlen(s + 1);
memset(dp, 0, sizeof dp);
for (int i = 1; i <= len; ++i)
dp[i][i] = 1;
for (int l = 2; l <= len; ++l) {
for (int i = 1; i + l <= len + 1; ++i) {
int j = i + l - 1;
dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + mod) % mod; //先不考虑两个端点是否一样,那么从两个状态转移过来,有减法防止出现负数取模之前先加一个mod
if (s[i] == s[j])
dp[i][j] = (dp[i][j] + dp[i + 1][j - 1] + 1) % mod; //两个端点一样还可以自己或者和[i+1,j-1]内的回文串组合
}
}
cout << dp[1][len] << endl;
}
//system("pause");
return 0;
}

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

char s[1005];
int dp[1005][1005];
int len;
const int mod = 1e4 + 7;

int func(int l, int r) {
if (dp[l][r] != 0 || l>=r) return dp[l][r]; //记忆化搜索+边界
dp[l][r] = (func(l + 1, r) + func(l, r - 1) - func(l + 1, r - 1) + mod) % mod;
if (s[l] == s[r])
dp[l][r] = (dp[l][r] + func(l + 1, r - 1) + 1) % mod;
return dp[l][r];
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
for (int cases = 1; cases <= t; ++cases) {
cout << "Case " << cases << ": ";
scanf("%s", (s + 1));
len = strlen(s + 1);
memset(dp, 0, sizeof dp);
for (int i = 1; i <= len; ++i)
dp[i][i] = 1;
cout << func(1, len) << endl;
}
//system("pause");
return 0;
}

String painter—区间DP

题意:存在两个长度相同的字符串 A 和 B,不同的字符代表不同的颜色,每次操作可以将 A 的一段连续的字符用同一个字符代替(即将 A 的一段用一种颜色覆盖),求将 A 涂成 B 至少需要多要操作

思路 参考博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

int dp[105][105];
int ans[105];

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
string a, b;
while (cin >> a >> b) {
int len = a.length();
//想尝试从空串涂到b串
for (int i = 0; i < len; ++i)
dp[i][i] = 1;
for (int l = 2; l <= len; ++l) {
for (int i = 0; i + l - 1 < len; ++i) {
int j = i + l - 1;
//如果枚举的位置和第一个位置的颜色相同那么就可以在涂第一个颜色的时候将j的位置也上了
dp[i][j] = dp[i + 1][j] + (b[i] != b[j]); //下面的枚集不能枚举到j所以这里提前看看能否在j处减少涂色步骤
for (int k = i; k < j; ++k) { //枚举k看看是够有可以减少涂色步数的方法
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (b[i] != b[k]));
}
}
}
//再尝试从a串涂到b串
ans[0] = (a[0] != b[0]);
for (int i = 1; i < len; ++i) {
ans[i] = dp[0][i]; //初始肯定超不过由空串涂到b用的次数
if (a[i] == b[i])
ans[i] = ans[i - 1];
else {
for (int j = 0; j < i; ++j)
ans[i] = min(ans[i], ans[j] + dp[j + 1][i]);
}
}
cout << ans[len - 1] << endl;
}
system("pause");
return 0;
}

You Are the One—区间DP

题意:有一个队列,其中每个人都有一个愤怒值 D,如果他是第 K 个登场的人那么不开心指数就是 (K-1)*D,现在有一个堆栈可以帮助你更改一段连续的人的出场顺序颠倒。求出借助堆栈操作后整个队列登场后不开心的指数最小是多少

思路:考虑用 dp[i][j] 表示第 i 到第 j 个人这段区间的相对 i 位置统计的最小不开心指数,统计出每个位置的人的愤怒值前缀和,然后枚举第 i 个人出去的位置为 k,那么第 i 个人的不开心值可知 (k-i)*a[i],有 k-1 个人是在 k 位置之前出去的,并且有 j-k 个人是在 k 位置之后出去的,他们公有一段不开心值为 (k-i+1)*(sum[j]-sum[k]),所以这段区间的转移方程为 dp[i][j]=min(dp[i][j],a[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j])

初始化合法区间值为最大,不合法区间相当于没人所以为 0,最终答案就是 dp[1][n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//dp[i][j]表示[i,j]这些人走出去和的最小,计算和也是相对于i的
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
using namespace std;
typedef long long ll;

int a[105],sum[105];
int dp[105][105];


signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
int t;cin>>t;
for(int cases=1;cases<=t;++cases){
int n;cin>>n;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(i<=j)dp[i][j]=0x3f3f3f3f;
else dp[i][j]=0;
}
}
for(int i=1;i<=n;++i){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int l=1;l<=n;++l){
for(int i=1;i+l<=n+1;++i){ //假设第i个人是第k个出去的
int j=i+l-1;
for(int k=i;k<=j;++k){
dp[i][j]=min(dp[i][j],a[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j]); //那么[i+1,k]在i之前出去,[i+k,j]在i之后出去
}
}
}
cout<<"Case #"<<cases<<": "<<dp[1][n]<<endl;
}
//system("pause");
return 0;
}