Skip to main content

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

January 29, 2019   

花店橱窗布置


思路

  • f[i][j]f[i][j]表示前i个花瓶前j个花束的最大美学价值
  • f[i][j]=max(f[i−1][k],f[i][j])f[i][j]=max(f[i−1][k],f[i][j])

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

  • 整张表都是向右下方走的,向下走加上数值,向右走无影响
  • 如果向下走代表花束放入花瓶,向右走无影响代表不放入
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的问题

传纸条


思路

  • f[i][j][k][l]f[i][j][k][l]表示现在去的到了(i,j),回来的到了(k,l)

  • 一共有四种情况,上上,左左,上左,左上

  • 保证两条路径不相交if(j1==j2 && i1==i2) continue

  • f[i][j][k][l]=max(f[i−1][j][k−1])f[i][j][k][l]=max(f[i−1][j][k−1])

  • 步数为i+j−1i+j−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]=ff[i][j]=f

三角蛋糕


思路

  • 像数字三角形一样压缩成正三角形
  • f[i][j]=min(f[i+1][j],f[i+1][j+1])+1f[i][j]=min(f[i+1][j],f[i+1][j+1])+1

金明的预算方案


思路:分组背包

  • 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,五种情况已经重新配置的前提下

01/完全背包混合


  • 根据物品的类型选择状态转移方程

二维限制的背包


  • 把数组扩展成三维
  • 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 求最大的价值

思路

  • 如果没有面包被压扁,就是一个完全背包问题
  • 如果有大面包,肯定要放到最上面,使得压缩高度尽可能大
  • 枚举最上面是哪一个大面包,然后其余所有面包的高度都变为原来的五分之四,就转化成了一半的完全背包问题