57
专题测试复习之动态规划
source link: https://beyondlimits.site/439.html?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
只考了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.保送
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK