专题测试复习之动态规划

只考了emmm100...

有点懵。

居然01背包维度写法出了问题。。。。

1.陈老师搬书

题目链接： https://www.luogu.org/problemnew/show/U36590

题目大意：给定3个书堆，给出堆中书的数量以及本书排放的次序，已知一个值 c 是从1向3堆书数量之和累加的，计算当前搬走几本书的劳累值即为c*本数，要求劳累值的总和最大，输出这个劳累值。

思考：这道题一眼看上去就是dp了。但是似乎贪心也可以。贪心思路为每一层选取本书最少的先搬，这样c就会累积，之后的值似乎也就更大了。 但是 ，有时会出现目前可以搬走的书中不是最小的值，可能下面藏了个更小的，这样即使c在累积，也不能保证一定是最大的。故贪心思路错误。那么我们试着用dp的思路来想：

我们可以设定一个 状态转移方程 ：

首先：

f[i][j][k]

表示第一堆搬走了i本，第二堆搬走了j本，第三堆搬走了k本时的最优解

显然，状态转移方程即为：

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#define fint(a,b,c) for(register int a=b;a<=c;a++)
#define fintre(a,b,c) for(register int a=b;a>=c;a--)
using namespace std;
long long a,b,c,f[101][101][101],a1[101],b1[101],c1[101];
int main()
{
  cin>>a>>b>>c;
  fintre(i,a,1) cin>>a1[i];
  fintre(i,b,1) cin>>b1[i];
  fintre(i,c,1) cin>>c1[i];
  fint(i,0,a)
    fint(j,0,b)
      fint(k,0,c)
      {
      	if(i>=1) f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+a1[i]*(i+j+k));
      	if(j>=1) f[i][j][k]=max(f[i][j][k],f[i][j-1][k]+b1[j]*(i+j+k));
      	if(k>=1) f[i][j][k]=max(f[i][j][k],f[i][j][k-1]+c1[k]*(i+j+k));
    }
  cout<<f[a][b][c]<<endl;
  return 0;
}

好像考试的时候就做出来这一道题。。太丢人了

2.保送

题目链接： https://www.luogu.org/problemnew/show/U36594