题目内容

P1233

一堆木头棍子共有 n 根,每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的:

第一根棍子的准备时间为 1 分钟;

如果刚处理完长度为 L,宽度为 W 的棍子,那么如果下一个棍子长度为 L_i,宽度为 W_i,并且满足 L\ge L_iW\ge W_i,这个棍子就不需要准备时间,否则需要 1 分钟的准备时间;

计算处理完 n 根棍子所需要的最短准备时间。比如,你有 5 根棍子,长度和宽度分别为 (4, 9),(5, 2),(2, 1),(3, 5),(1, 4),最短准备时间为 2(按 (4, 9)、(3, 5)、(1, 4)、(5, 2)、(2, 1) 的次序进行加工)。

解题思路

可以先贪心,后 dp,将所有的木棍先按照长度从大到小排序,如果长度相同就排宽度,然后就可以参考导弹拦截:由 Dilworth 定理,最大不上升子序列的个数为最大上升子序列的长度,因此我们只需要找到宽度的最长上升子序列就可以了。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;

struct stick
{
    int l,w;
}a[5005];

int f[5005];

inline bool cmp(stick a,stick b)
{
    return a.l==b.l?a.w>b.w:a.l>b.l;
}

int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&a[i].l,&a[i].w);
    sort(a+1,a+n+1,cmp);
    int len=1;
    f[1]=a[1].w;
    for(int i=2;i<=n;i++)
    {
        if(a[i].w>f[len])
            f[++len]=a[i].w;
        else
        {
            int p=lower_bound(f+1,f+len+1,a[i].w)-f;
            f[p]=a[i].w;
        }
    }
    printf("%d\n",len);
    return 0;
}
最后修改日期:2020年3月14日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。