状态转移：见代码

for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
        f[i][j][0]=f[i][j][1]=INF;
f[v][v][0]=f[v][v][1]=0;
for(int l=2;l<=n;l++)
{
    for(int i=1;i<=n-l+1;i++)
    {
        int j=i+l-1;
        if(f[i][j][0]>f[i+1][j][0]+(d[i+1]-d[i])*p[i+1][j])
            f[i][j][0]=f[i+1][j][0]+(d[i+1]-d[i])*p[i+1][j];
        if(f[i][j][0]>f[i+1][j][1]+(d[j]-d[i])*p[i+1][j])
            f[i][j][0]=f[i+1][j][1]+(d[j]-d[i])*p[i+1][j];
        if(f[i][j][1]>f[i][j-1][1]+(d[j]-d[j-1])*p[i][j-1])
            f[i][j][1]=f[i][j-1][1]+(d[j]-d[j-1])*p[i][j-1];
        if(f[i][j][1]>f[i][j-1][0]+(d[j]-d[i])*p[i][j-1])
            f[i][j][1]=f[i][j-1][0]+(d[j]-d[i])*p[i][j-1];
    }
}
if(f[1][n][0]>f[1][n][1]) printf("%d\n",f[1][n][1]);
else printf("%d\n",f[1][n][0]);

练习1：矩阵连乘

给定 \(n\) 个矩阵 \(\{ A_1, A_2, \cdots , A_n \}\)，考察这 \(n\) 个矩阵的连乘积$ A_1A_2 \cdots An$ 。

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，

这种计算次序可以用加括号的方式来确定。矩阵连乘积的计算次序与其计算量有密切关系。

例如，考察计算 \(3\) 个矩阵$ { A_1, A_2, A_3 }$ 连乘积的例子。

设这3个矩阵的维数分别为 \(10 \times 100\)，\(100 \times 5\) 和 \(5 \times 50\) 。

若按 \((A1A2)A3\) 计算，\(3\) 个矩阵连乘共需要 \(10 \times 100 \times 5+10 \times 5 \times 50=7500\) 次数乘。

若按 \(A1(A2A3)\) 计算，则总共需要 \(100 \times 5 \times 50+10 \times 100 \times 50=75000\) 次数乘。

现在你的任务是给出一个矩阵连乘式，计算其需要的最少乘法次数。

练习2：矩阵取数游戏 Luogu P1005 [NOIP2007 提高组]

练习3：AtCoder Express 2 AtCoder ABC106D

练习4：玩具取名 Luogu P4290 [HAOI2008]

练习5：监狱

小X的王国中有一个奇怪的监狱，这个监狱一共有 \(P\) 个牢房，这些牢房一字排开，

第 \(i\) 个仅挨着第 \(i+1\) 个（最后一个除外），当然第 \(i\) 个也挨着第 \(i?1\) 个（第一个除外），

现在牢房正好是满员的。上级下发了一个释放名单，要求每天释放名单上的一个人。

这可把看守们吓得不轻，因为看守们知道，现在牢房里的 \(P\) 个人，

可以相互之间传话。第 \(i\) 个人可以把话传给第 \(i+1\) 个，当然也能传给第 \(i?1\) 个，

并且犯人很乐意把消息传递下去。

如果某个人离开了，那么原来和这个人能说上话的人，都会很气愤，

导致他们那天会一直大吼大叫，搞得看守很头疼。

如果给这些要发火的人吃上肉，他们就会安静下来。

为了河蟹社会，现在看守们想知道，如何安排释放的顺序，才能是的他们消耗的肉钱最少。

练习6：游戏 A Game Luogu P2734 [USACO3.3]

（六）双进程类动态规划

例题1：最长公共子序列

字符序列的子序列是指：

从给定字符序列中随意地（不一定连续）去掉若干个字符，

也可能一个也不去掉，去掉后所形成的字符序列为 字符序列的子序列。

令给定的字符序列\(X=\{x_0,x_1,\cdots ,x_{m-1}\}\)，序列\(Y=\{y_0,y_1,\cdots ,y_{k-1}\}\) 是 \(X\) 的子序列，

存在 \(X\) 的一个严格递增下标序列 \(\{i_0,i_1,\cdots,i_{k-1}\}\) ，

使得对所有的\(j=0,1,\cdots,k-1\) ，有 \(x_{ij}=y_j\) 。

例如，\(X=\verb!"ABCBDAB"!\) ，\(Y=\verb!"BCDB"!\) 是 \(X\) 的一个子序列。

对给定的两个字符序列，求出他们最长的公共子序列长度。

状态：\(f[i][j]\)：\(X\) 的前 \(i\) 位和 \(Y\) 的前 \(j\) 位所构成的最长公共子序列的长度

状态转移：\(f[i][j]=max(f[i][j-1],f[i-1][j])\)

for(int i=1;i<=len1;i++)
{
    for(int j=1;j<=len2;j++)
    {
        f[i][j]=max(f[i][j-1],f[i-1][j]);
        if(s1[i]==s2[j]&&f[i][j]<=f[i-1][j-1]) f[i][j]++;
        ans=max(ans,f[i][j]);
    }
}
printf("%d\n",ans);

例题2：配置魔药

魔药课，Snape要他们每人配置一种魔药（不一定是一样的），现在Harry面前有两个坩埚，

有许多种药材要放进坩埚里，但坩埚的能力有限，无法同时配置所有的药材。

一个坩埚相同时间内只能加工一种药材，但是不一定每一种药材都要加进坩埚里。

加工每种药材都有必须在一个起始时间和结束时间内完成

（起始时间所在的那一刻和结束时间所在的那一刻也算在完成时间内）

每种药材都有一个加工后的药效，现在要求的就是Harry可以得到最大的药效。

状态：\(f[i][j][k]\)：前 \(i\) 种草药，第一个坩埚用时 \(j\)，第二个坩埚用时 \(k\) 能得到的最大功效

状态转移：当 \(j \geq a[i].t2\) 时，\(f[j][k]=max(f[j][k],f[a[i].t1-1][k]+a[i].w)\)

? 当 \(k \geq a[i].t2\) 时，\(if(k>=a[i].t2) f[j][k]=max(f[j][k],f[j][a[i].t1-1]+a[i].w)\)

bool mycmp(node a,node b)
{
	return a.t2<b.t2;
}