↓Skip to main content

动态规划习题2

December 31, 2018   
Learn / Competitive Programming
Table of Contents

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;

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

    然后我就想找到最后一个状态是从哪里转移过来的，最后再额外判断一遍。虽然有点不像动态规划，只要用last1，last2两个变量储存倒数第二个和第三个留下的点，但还是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，因为落差的区间变大了，能够容纳的合法的花也变多了；同理，如果B比A还小，那么一定会选择B
    • 通过以上两个判断不停地找波峰和波谷，记录答案就可以了

P1020 导弹拦截

*非常恶心的一道题，我已经被搞晕了*

分析

  • 第一问就是求最长不上升子序列，想象有一个栈，如果当前数小于等于栈顶的数，则直接入栈；否则二分查找栈内第一个大于等于当前数的数并替换它，因为与当前数相等的数是有贡献的
  • 第二问就是求最长上升子序列，我不会证明，只能大概的胡诌，因为相当于我只关心子序列的长度，而只要有一个高度大于当前长度，就必须去新建一个序列，有点类似于木桶原理……

遇到的坑

  • 最长不下降子序列 等价于 倒序的最长不上升子序列
  • 最长下降子序列 等价于 倒序的最长上升子序列
  • lower_bound 二分查找第一个大于等于基准数的数（涵盖的范围更广）
  • upper_bound 二分查找第一个大于基准数的数

P1103 书本整理

*很有感触的一道题*

分析

  • 可以抽象为：给定一串数列，首先对数列进行排序，**然后从数列中删除K个数使得整个数列每相邻两个数的差的绝对值的和最小，**输出最小的和，即最小不整齐度。好拗口

  • f[i][j]表示长度为j的数列，数列最后一个的位置标号为j

  • 假设当前状态数列长度为j，现在以第i位为数列的最后一个，即最后一个肯定留下的最小不整齐度。因为这一位肯定要保留，所以状态肯定是从j-1转移过来的。其次我们就要枚举数列长度为j-1时，数列最后一个保留的数到底是多少，由此我们可以计算出应该增加的不整齐度

  • 转移方程：

    f[i][j]=min(f[t][j-1]+abs(a[i]-a[t]),f[i][j]);//最后一个保留a[i],数列长度为j的最小不整洁度

  • 接下来考虑边界问题

    • j<=i 序列里的数肯定不会超过所有当前的数
    • t>=j-1 由上式同理可以得出，状态中的第一维度肯定大于等于第二维度
    • t<i 数列里的最后一个数肯定不可能达到现在及以后的数
    • j<=n-K 由题意可得……

    分析最清晰的一回

遇到的坑

  • **f[n][n-k]并不是最终答案！！！**只要状态里最后一个位置编号大于n-K，并且序列里有n-K个数，就有可能成为答案，所以我们要扫一遍找到最终答案
  • 赋初值！！！ 因为我们状态转移选择的是最小值，最开始所有状态都是0，无论怎么转移都是0。所以我们把所有初值赋值为无穷大？显然不可行。我们可以每当需要转移该状态时，在确定该状态一定会被改变的前提下提前赋值为无穷大****
  • 真的都是很深很深的坑

AC代码

//与前文所使用的变量名有所不同
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=110;
struct ty
{
    int h,w;
};
ty b[N];
int n,K,f[N][N];//是否保留 

bool operator < (const ty &a,const ty &b)
{
    return a.h<b.h;
}

int main()
{
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&b[i].h,&b[i].w);
    
    K=n-K;
    sort(b+1,b+n+1);
    
    //第i个数保留j个的最小整齐度,序列的最后一个数序号为i 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=K&&j<=i;j++)
        {
            if(j==1) continue;
            f[i][j]=0x3f3f3f3f;
            for(int t=j-1;t<i;t++)
            {
                f[i][j]=min(f[t][j-1]+abs(b[i].w-b[t].w),f[i][j]);
            }
//			printf("f[%d][%d]=%d\n",i,j,f[i][j]);
        }
    }
    
    int ans=0x3f3f3f3f;
    for(int i=K;i<=n;i++)
        ans=min(ans,f[i][K]);
    printf("%d\n",ans);
    return 0;
}
  
#algorithm
↑