济南Day3 坐标型动态规划及背包

Table of Contents

花店橱窗布置

当然还有另外一种思路(*太强了！！！*)：

int f[N][N],mp[N][N];
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
        f[i][j]=max(f[i-1][j]+mp[i][j],f[i][j-1]);

因为每次取头和尾，所以一定是一个连续的区间
f[i][j]f[i][j]表示从i取到j的最大得分
$f[i][j]=max(f[i][j-1]+a[j]*2^(i-1+n-j+1+1) \ , \ f[i-1][j]+a[i]*2^(i-1+n-j+1+1))$
指数是轮数，当前数前面有多少个数被取走，就有多少轮，注意一下1的问题

判断不合法的状态

if(i1+j1!=i2+j2) continue;
if(i1==i2 && j1==j2 && i1+j1!=2 && i1+j1!=m+n) f[i1][j1][i2][j2]=-0x3f3f3f3f;

当m,n<100m,n<100时，四维数组开不下了，因为i1+j1=i2+j2i1+j1=i2+j2的时候才是合法的，并且三个数都确定时，我们可以直接算出j2j2,直接变成了三维

地面长度为L，高度为H，天上掉馅饼
人在地上每单位时间可以向左或向右移动0~2格，馅饼每单位时间掉落一格
求最多接到多少馅饼（馅饼有分值）

f[i][j]f[i][j]表示前i组物品重量不超过j的最大价值
一共5种转移方式
f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5,五种情况已经重新配置的前提下

把数组扩展成三维
f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])

有N种面包，每种面包数量无限多，有高度和价值，高度是5的倍数将面包叠成一个面包塔，高度不得超过T 给定常数k，若一个面包高度>=k，则它下面所有面包都会被压扁一个面包最多被压扁一次，它的高度变为原来的4/5 求最大的价值