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

花店橱窗布置


思路

  • $f[i][j]$表示前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]$表示从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的问题

济南 Day2

动态规划

最长公共子序列


$O(nlogn)$做法: 转换成最长不下降子序列

具体做法: 数组b[i]表示当前长度为i最长不下降子序列

  • 如果$c_i \ge a[len]$ 那么就可以构造更长的序列,所以$len++, \ b[len]=c[i]$
  • 否则我们就要把$c_i$插入到之前的序列当中,找到第一个大于它的并替换掉

乘积最大


区间DP

状态:$f[i][j]$表示前i个数,有j个乘号的最大乘积

转移方程:$f[i][j]=max(f[k][j-1]*num[k+1][i]), \ k<i$

需要用到高精乘

三角形牧场

P1284三角形牧场


题意

现在有n段木棍,全部使用组成三角形的三条边,使三角形的面积最大

分析

  • 首先看数据范围,边长最大为40*40/3,并且因为要使用所有的木棍,所以只要两条边确定就可以知道第三条边的确定长度。因此我们可以设状态f[i][j]表示三角形的两条边分别是i,j的情况是否成立

  • $$f[i][j]=f[i-a[k]][j] \ || \ f[i][j-a[k]] \ || \ f[i][j]$$,相当于01背包,就不解释了……

  • 定义初始状态$f[0][0]=1$

  • 三条边都知道了,如何求面积呢?这里我们需要用到海伦公式

    $$S=\sqrt{p(p-a)(p-b)(p-c)} $$,$p=\frac{1}{2}(a+b+c)$

遇到的坑

好像没有什么

动态规划习题2

P1970 花匠


分析

  • 第一次很容易就能想到转移方程:

    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i]=f[i-1]+1;
    else if(a[i]<a[i+1] && a[i]<a[i-1]) f[i]=f[i-1]+1;

    但是这样做有一个很大的问题,无法确定最后一个状态的转移是否合法

    然后我就想找到最后一个状态是从哪里转移过来的,最后再额外判断一遍。虽然有点不像动态规划,只要用last1last2两个变量储存倒数第二个和第三个留下的点,但还是WA了2个点。

    原因好像是我丢掉了一些状态:我默认了只要这棵花能选就选,不满足无后效性

  • 动态规划

    正解:一维无法解决问题,那么就升一维。

    定义状态为f[i][j]表示第i个花处在上升或下降序列中能选的最多的花数

    状态转移方程为

    if(a[i]<a[i+1] && a[i]<a[i-1]) f[i][0]=f[i-1][1]+1;
    else f[i][0]=f[i-1][0];
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i][1]=f[i-1][0]+1;
    else f[i][1]=f[i-1][1];
  • 贪心

    为了方便我们设当前的花为A,下一盆花为B

    • 第一盆花肯定要选,如果不选的话第二盆就成了第一盆,花的总数就会减少,一定不会比选第一盆花更优
    • 如果B比A还高,那么一定会选择B,因为落差的区间变大了,能够容纳的合法的花也变多了;同理,如果BA还小,那么一定会选择B
    • 通过以上两个判断不停地找波峰和波谷,记录答案就可以了

动态规划习题1

P1504 积木城堡


分析

  • 最终的高度最高为所有城堡现有高度的最小值
  • 把每个城堡当做一个背包,每一块积木放入背包,求出该城堡能够组成的所有背包体积
  • 把背包体积进行统计,所有城堡统计完后扫一遍找到最大的都能满足的体积

遇到的坑

  • 高度重复累计
  • 枚举体积的循环从右往左枚举,每一次状态转移使用上一层左边的量,如果从右往左枚举就是相当于每个零件有无数个
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×