a+1+n,mycmp);
for(int i=1;i<=n;i++)
{
for(int j=t;j>=0;j--)
{
for(int k=t;k>=0;k--)
{
if(j>=a[i].t2) f[j][k]=max(f[j][k],f[a[i].t1-1][k]+a[i].w);
if(k>=a[i].t2) f[j][k]=max(f[j][k],f[j][a[i].t1-1]+a[i].w);
}
}
}
printf("%d\n",f[t][t]);
练习1:编辑距离 Luogu P2758
状态:\(f[i][j]\):字符串 \(A\) 的前 \(i\) 个字符变为字符串 \(B\) 的前 \(j\) 个需要的最少步数
状态转移:
\(delete:f[i][j]=min(f[i][j],f[i-1][j]+1);\)
\(input:f[i][j]=min(f[i][j],f[i][j-1]+1);\)
\(change:f[i][j]=min(f[i][j],f[i-1][j-1]+1);\)
\(none:f[i][j]=min(f[i][j],f[i-1][j-1]);\)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=INF;
for(int i=0;i<=n;i++)
f[i][0]=i;
for(int i=0;i<=m;i++)
f[0][i]=i;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//delete ABCD ABC
f[i][j]=min(f[i][j],f[i-1][j]+1);
//input ABC ABCD
f[i][j]=min(f[i][j],f[i][j-1]+1);
//change ABCE ABCD
if(s1[i]!=s2[j]) f[i][j]=min(f[i][j],f[i-1][j-1]+1);
//none ABCD ABCD
else f[i][j]=min(f[i][j],f[i-1][j-1]);
}
}
cout<<f[n][m]<<endl;
练习2:交错匹配
有两行自然数,\(up[1 \sim n]\),\(down[1 \sim n]\),如果 \(up[i]=down[j]=k\),
那么上行的第 \(i\) 个位置的数就可以跟下行的第 \(j\) 个位置的数连一条线,称为一条 \(K\) 匹配,
但是同一个位置的数最多只能连一条线。
另外,每个 \(k\) 匹配都必须且至多跟一个 \(l\) 匹配相交且 \(k \neq l\) 。现在要求一个最大的匹配数。
例如:以下两行数的最大匹配数为 \(8\)
(七)二维动态规划
例题1:过河卒 Luogu P1002 [NOIP2002 普及组]
用 \(vis\) 数组标记马能到达的坐标
状态:\(f[i][j]\):到达点 \((i,j)\) 的路径数目
状态转移:\(f[i][j]=f[i-1][j]+f[i][j-1]\)
for(int i=0;i<=yb;i++)
if(vis[0][i]) break;
else f[0][i]=1;
for(int i=0;i<=xb;i++)
if(vis[i][0]) break;
else f[i][0]=1;
for(int i=1;i<=xb;i++)
{
for(int j=1;j<=yb;j++)
{
if(vis[i][j]) f[i][j]=0;
else f[i][j]=f[i-1][j]+f[i][j-1];
}
}
printf("%d\n",f[xb][yb]);
例题2:传纸条 Luogu P1006 [NOIP2008 提高组]
状态:\(f[i][j][k][l]\):第一个纸条传到了 \((i,j)\),第二个纸条传到了 \((k,l)\) 的时候能获得的最优值
我们发现,四维状态会枚举许多不会出现的状态
当两个纸条同步的时候,在某个时间,他们所处的两个位置行列之和是相等的
因为他们走的步数是一样的,由此,得到如下状态:
状态:\(f[p][i][j]\):当前走了 \(p\) 步,第一个个人走到第 \(i\) 行,第二个人走到第 \(j\) 行的最大价值
状态转移:
\[f[k][i][j]=max(max(f[k-1][i][j],f[k-1][i-1][j]),\\ max(f[k-1][i][j-1],f[k-1][i-1][j-1]))+a[i][k-(i-1)]+a[j][k-(j-1)]; \]
for(int k=1;k<=m+n-1;k++)
{
for(int i=1;i<=m;i++)
{
for(int j=i+1;j<=m;j++)
{
if(i>k||j>k) continue;
f[k][i][j]=max(max(f[k-1][i][j],f[k-1][i-1][j]),max(f[k-1][i][j-1],f[k-1][i-1][j-1]))+a[i][k-(i-1)]+a[j][k-(j-1)];
}
}
}
printf("%d\n",max(f[n+m-1][m][m-1],f[n+m-1][m-1][m]));
例题3:农田个数
你的老家在农村。过年时,你回老家去拜年。
你家有一片 \(N \times M\) 农田,将其看成一个 \(N \times M\) 的方格矩阵,有些方格是一片水域。
你的农村伯伯听说你是学计算机的,给你出了一道题:
他问你:这片农田总共包含了多少个不存在水域的正方形农田。
两个正方形农田不同必须至少包含下面的两个条件中的一条:
- 边长不相等
- 左上角的方格不是同一方格
状态:\(f[i][j]\):以方格 \((i,j)\) 为右下角,可以得到的最大无正方形边长
状态:\(f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1\)
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==0) f[i][j]=0;
else f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
ans+=f[i][j];
}
}
printf("%d\n",ans);
练习1:矩阵切割
给你一个矩阵,其边长均为整数。
你想把矩阵切割成总数最少的正方形,其边长也为整数。
切割工作由一台切割机器完成,
它能沿平行于矩形任一边的方向,从一边开始一直切割到另一边。
对得到的矩形再分别进行切割。
练习2:创意吃鱼法 Luogu P1736
练习3:方格取数 Luogu P1004 [NOIP2000 提高组]
练习4:方格取数 Luogu P7074 [CSP-J2020]
练习5:滑雪 Luogu P1434 [SHOI2002]