前言


​       某位大佬曾经说过,dp不会没问题,想不到状态转移方程没问题,多做题就会了。所以,我打算多刷点dp题。那么,先从基础刷起吧。

1. P1091 合唱队形


题意

​       已知序列 $a$ 有 $n$ 个数,通过取出其中一些数可以使他满足严格的先增再减序列,问最少取出几个。


思路

​       很显然想要求最少取出几个,我们就看严格先增再减的序列的最长长度即可。我们可以用 $g[i]$ 来存储到 $a[i]$ 为止的最长递增子序列的长度,然后用 $l[i]$ 来存储从 $a[i]$ 到序列末尾最长的递减子序列的长度。处理 $g[i]$ 从前往后扫,处理 $l[i]$ 需要从后往前扫。处理完 $f$ 和 $g$ 数组那么就从左到右扫一遍,$ans=max(ans,g[i]+l[i]-1)$ 。答案即是 $n-ans$ 。


代码实现

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>

using namespace std;

const int maxn=105;
int n;
int a[maxn],g[maxn],l[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(a[i]>a[j]) g[i]=max(g[i],g[j]+1);
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=n+1;j>i;j--)
        {
            if(a[i]>a[j]) l[i]=max(l[i],l[j]+1);
        }
    }
    int maxout=0;
    for(int i=1;i<=n;i++)
    {
        maxout=max(maxout,g[i]+l[i]-1);
    }
    printf("%d",n-maxout);
    return 0;
} 

2. P1280 尼克的任务


题意

​       尼克的一个工作日为 $n$ 分钟,从第一分钟开始到第 $n$ 分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成,尼克可以任选其中的一个来做,而其余的则由他的同事完成,反之如果只有一个任务,则该任务必需由尼克去完成,假如某些任务开始时刻尼克正在工作,则这些任务也由尼克的同事完成。如果某任务于第 $p$ 分钟开始,持续时间为 $t$ 分钟,则该任务将在第 $p+t-1$ 分钟结束。(实在不会总结题意,就直接复制过来了)


思路

​       我们可以设 $f[i]$ 为时间从 $i\sim n$ 所能获得最长空闲时间,最终 $f[1]$ 对应的就是答案。假设在这个 $i$ 分钟有 $k[i]$ 个任务可以,那么我们可以分以下情况转移

  • $k[i]=0$ , 那么 $f[i]=f[i+1]+1$
  • $k[i]\not=0$ ,那么可以循环 $1 \sim k[i]$ 遍历这个时间点开始的任务,$f[i]=max(f[i],f[i+k[i].t])$

​       思路是这样的,但是我们记录 $k[i].t$ 并不好记录,因此我们可以先将任务开始时间按降序排序,用一个一个变量 $cnt$ 来代表已经取到第几个任务了,那么这样一直取下去,最终就能够遍历所有的任务。


代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=10005;
struct task
{
    int l,r;
}t[maxn];
int cmp(struct task a,struct task b)
{
    return a.l>b.l;
}
int dp[maxn];
int p[maxn];
int cnt=1,n,k; 
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&t[i].l,&t[i].r);
        p[t[i].l]++;
    }
    sort(t+1,t+1+k,cmp);
    for(int i=n;i>=1;i--)
    {
        if(!p[i])
        {
            dp[i]=dp[i+1]+1;
        }
        else 
        {
            for(int j=1;j<=p[i];j++)
            {
                dp[i]=max(dp[i],dp[i+t[cnt].r]);
                cnt++;
            }
        }
    }
    printf("%d\n",dp[1]);
    return 0;
}

​       我太懒了····就写了两道,明天继续加油吧。。

最后修改:2020 年 08 月 18 日 12 : 29 AM
如果觉得我的文章对你有用,请随意赞赏