练习：最少硬币问题

设有 \(n\) 种不同面值的硬币，各硬币的面值存于数组 \(T[1 \sim n]\) 中。现要

用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 $Coins [1 \sim n] $ 中。

对任意钱数 \(0 \leq m \leq 20001\)，设计一个用最少硬币找钱 \(m\) 的方法。

对于给定的 \(1 \leq n \leq 10\)，硬币面值数组 \(T\) 和可以使用的各种面值的硬币个数数组 \(Coins\)，

以及钱数 \(m\)，\(0 \leq m \leq 20001\)，编程计算找钱 \(m\) 的最少硬币数。

四、多维费用背包

例题：NASA的食物计划 Luogu P1507

按照 01背包 的表示方法，加一维进行表示即可。

状态：\(f[i][j][k]\)：前 \(i\) 个物品付出代价分别为 \(c\) 和 \(u\) 时可以获得的最大价值

状态转移：\(f[i][j][k]=max(f[i][j][k],f[i-1][j-v[i]][k-m[i]]+w[i])\)

for(int k=1;k<=n;k++)
{
    for(int i=V;i>=1;i--)
    {
        for(int j=M;j>=1;j--)
        {
            if(i-v[k]>=0&&j-m[k]>=0)
                f[i][j]=max(f[i][j],f[i-v[k]][j-m[k]]+c[k]);
        }
    }
}
printf("%d\n",f[V][M]);

练习：潜水员的规划

潜水员为了潜水要使用特殊的装备。他有一个带 \(2\) 种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种的数量的氧和氮。

潜水员有一定数量的气缸，每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有 \(5\) 个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

\(3 \ 36 \ 120\)

\(10 \ 25 \ 129\)

\(5 \ 50 \ 250\)

\(1 \ 45 \ 130\)

\(4 \ 20 \ 119\)

如果潜水员需要 \(5\) 升的氧和 \(60\) 升的氮则总重最小为 \(249\) （\(1,2\) 或者 \(4,5\) 号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

五、分组背包

例题：竞赛真理

根据每一题解题时间的估计值，确定一种做题方案

即哪些题目认真做，哪些题目 “骗” 分，哪些不做，使能在限定的时间内获得最高的得分。

状态：\(f[k][j]\)：前 \(k\) 组物品花费 \(j\) 时可以获得的最大价值

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

按照 01背包，第一维可以省略。

for(int k=1;k<=n;k++)
{
    for(int c=t;c>=0;c--)
    {
        if(c-t1[k]>=0) f[c]=max(f[c],f[c-t1[k]]+w1[k]);
        if(c-t2[k]>=0) f[c]=max(f[c],f[c-t2[k]]+w2[k]);
    }
}
printf("%d\n",f[t]);

（五）区间动态规划

例题1：石子合并（弱化版） Luogu P1775

状态：\(f[i][j]\)：从第 \(i\) 堆石子到第 \(j\) 堆石子，合并成为一堆石子的最小得分

状态转移：\(f[i][j]=f[i][k]+f[k+1][j]+sum[j]-sum[i-1]\)

for(int p=1;p<=n;p++)
{
    for(int i=1;i<=n;i++)
    {
        int j=i+p-1;
        if(j>n) break;
        for(int k=i;k<j;k++)
            if(f[i][j]>f[i][k]+f[k+1][j]+sum[j]-sum[i-1]||f[i][j]==0)
                f[i][j]=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
    }
}
printf("%d\n",f[1][n]); 

例题2：环形石子合并

将 \(n\) 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 \(n\) 及每堆的石子数，并进行如下计算：

1. 选择一种合并石子的方案，使得做 \(n?1\) 次合并得分总和最大。
2. 选择一种合并石子的方案，使得做 \(n?1\) 次合并得分总和最小。

与上题相同，仅需把环转换成链即可。

例题3：能量项链 Luogu P1063 [NOIP2006 提高组]

状态：\(f[i][j]\)：从 \(i\) 到 \(j\) 的最大释放能量

状态转移：\(f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1])\)

for(int p=1;p<=2*n;p++)
{
    for(int i=1;i<=2*n-p+1;i++)
    {
        int j=i+p-1;
        if(j>2*n) break;
        for(int k=i;k<j;k++)
            f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
    }
}
for(int i=1;i<=n;i++)
    ans=max(ans,f[i][i+n-1]);
printf("%d\n",ans); 

例题4：关灯

宁智贤得到了一份有趣而高薪的工作。每天早晨她必须关掉她所在村庄的街灯。

所有的街灯都被设置在一条直路的同一侧。

宁智贤每晚到早晨5点钟都在晚会上，然后她开始关灯。

开始时，她站在某一盏路灯的旁边，每盏灯都有一个给定功率的电灯泡

因为宁智贤有着自觉的节能意识，她希望在耗能总数最少的情况下将所有的灯关掉。

宁智贤因为太累了，所以只能以 \(1m / s\)的速度行走。

关灯不需要花费额外的时间，因为当她通过时就能将灯关掉。

计算在给定路灯设置，灯泡功率以及宁智贤的起始位置的情况下，

关掉所有的灯需耗费的最小能量。

状态：\(f[i][j]\)：从第 \(i\) 号灯到第 \(j\) 号灯全部关闭的最小能量

而对于这个状态来说，人将这个区间的灯全部关闭之后

只有处于这个区间两端的时候，才有可能是最优方案，所以，得到如下状态：

状态：\(f[i][j][0]\)：关闭区间 \([i,j]\) 中的灯之后，人在左端点的最小能量

? \(f[i][j][1]\)：关闭区间 \([i,j]\) 中的灯之后，人在右端点的最小能量

预处理：\(p[i][j]\)：关闭区间 \([i,j]\) 中的的灯之后，其他灯的单位时间消耗