• 涉及到区间划分的问题可以归到此类
  • 区间问题大多相似,都是枚举划分点,然后选择最优子结构

最优矩阵链乘

  • 矩阵相乘规则:两个矩阵,$n \times m , m \times p$相乘的运算量为$nmp$
    给出一个n个矩阵组成的序列,选择一种相乘顺序使总运算量尽量小,第i个矩阵表示为 m[i-1]×m[i]
    f(i,j) 表示矩阵i到j相乘所需的最小运算量

$$f(i,j)=Min\left(f(i,k)+f(k+1,j)+m[i-1]m[k]m[j]\right) \,\,\,\, k\in[i,j) \,\, f(i,i)=0$$

两种实现

  • 注意n为矩阵个数

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
ll dp(int i,int j)
{
if(i==j) return 0;
ll &ans=d[i][j];
if(ans) return ans;
ans=INF;
for(int k=i;k<j;++k)
ans=min(ans,dp(i,k)+dp(k+1,j)+m[i-1]*m[k]*m[j]);
return ans;
}
dp(1,n);

递推

应按照j-i递增顺序递推,因为长区间的值依赖于短区间的值

1
2
3
4
5
6
7
8
9
10
11
12
13
ll dp(int n)
{
for(int i=1;i<=n;++i) d[i][i]=0;
for(int L=2; L<=n;++L)
for(int i=1; i<=n-L+1 ; ++i){
int j=i+L-1; // j-i=L-1
d[i][j]=INF;
for(int k=i;k<j;++k)
d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+m[i-1]*m[k]*m[j]);
}
return d[1][n];
}
dp(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
for(int k=i;k<j;++k){
ll t=min(d[i][j],d[i][k]+d[k+1][j]+m[i-1]*m[k]*m[j]);
if(d[i][j]>t){
d[i][j]=t;
p[i-1][j]=k; //记录乘法位置
}
}

vector<int> ans;
void print(int i,int j)
{
if(!p[i][j]) return ;
print(i,p[i][j]);
print(p[i][j],j);
ans.push_back(p[i][j]);
//printf("%d ",p[i][j]);
}
print(0,n);

for(int i=1;i<=n;++i) pl[i]=pr[i]=1;
for(int j=0;j<ans.size();++j){
int i=ans[j];
int lf=pl[i];
int rt=pr[pr[i]+1];
pr[lf]=rt;
pl[rt]=lf;
l[lf]++;
r[rt]++;
}

for(int i=1;i<=n;++i){
while(l[i]){
printf("(");--l[i];
}
printf("Matrix[%d]",i);
while(r[i]){
printf(")");--r[i];
}
if(i<n) printf(" x ");
}

最优三角剖分

将一个n个顶点的凸多边形中用n-3条互不相交的对角线将其划分为n-2个三角形,使w(i,j,k)(每一个三角形的权函数)最大
定义d(i,j)为子多边形i,i+1,…,j (i<j) 的最优解,则中间存在一个三角形 i-k-j (i<k<j)
最后的解为 d(0,n-1)

$$d(i,j)=Max(d(i,k)+d(k,j)+w(i,j,k) \,\, | \,\, i<k<j) \,\,\,\, d(i,i+1)=0$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//记忆化搜索
memset(vis,0,sizeof(vis));
int dp(int i,int j)
{
if(j-i<=1) return 0;
int& ans=d[i][j];
if(vis[i][j]) return ans;
vis[i][j]=1;
ans=0;
for(int k=i+1;k<j;++k)
ans=max(ans,d(i,k)+d(j,k)+w(i,j,k));
return ans;
}

//递推
for(int l=1;l<n;++l)
for(int i=0;i+l<n;++i){
int j=i+l;
if(j==i+1) d[i][j]=0;
else
for(int k=i+1;k<j;++k)
d[i][j]=max(d[i][j],d[i][k]+d[k][j]+w(i,j,k));
}

多种决策

经典的括号匹配问题:

1.空串
2.s -> [s],(s)
3.s,s’-> ss’

根据题目可知两种转移:

1.[s] 转移到 s
2.s 至少有两个字符ab 转移到ab

  • 无论如何两种转移都要进行 因为这种情况 [][] 转移到了][
  • 用d[i][j]表示i~j最少需要添加字符
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
const int maxn=100 + 5;
int n;
char S[maxn];
int d[maxn][maxn]; //表示i~j至少需要添加多少括号

bool match(char a,char b)
{
return (a=='[' && b==']') || (a=='(' && b==')');
}

void dp()
{
for(int i=0;i<n;++i){
d[i+1][i]=0;
d[i][i]=1;
}

for(int i=n-2;i>=0;--i)
for(int j=i+1;j<n;++j){
d[i][j]=n;
if(match(S[i],S[j])) d[i][j]=min(d[i][j],d[i+1][j-1]);
for(int k=i;k<j;++k)
d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);
}
}

void print(int i,int j) //print(0,n-1)
{
if(i>j) return ;
if(i==j) {
if(S[i]=='(' || S[i]==')') printf("()");
else printf("[]");
return;
}
int ans=d[i][j];
if(match(S[i],S[j]) && ans==d[i+1][j-1]){
printf("%c",S[i]);
print(i+1,j-1);
printf("%c",S[j]);
return;
}
for(int k=i;k<j;++k)
if(ans==d[i][k]+d[k+1][j]){
print(i,k);
print(k+1,j);
return;
}
}