tofacebook.com -专业IT技术社区(贪吃蛇学院) 【百家号】脸书百科,bzoj 1029 [JSOI2007]建筑抢修——贪心(伪dp) Web程序 - 贪吃蛇学院-专业IT技术平台
78°

【百家号】脸书百科,bzoj 1029 [JSOI2007]建筑抢修——贪心(伪dp) Web程序

标签:php   就是   line   namespace   思考   amp   iostream   保留   tar   

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1029

当然要按结束时间排序,然后按顺序修或跳过。就是那种“……不会使答案不优”的证明。

想了一个dp。dp[ i ][ j ]表示前 i 个建筑、修了 j 个建筑,完成的最早时间。可惜是n^2的。

dp[ i ][ j ]=min( dp[ i-1 ][ j ] , dp[ i-1 ][ j-1 ]+len[ i ] )   (dp[ i-1 ][ j-1 ]+len[ i ]<=t[ i ])

考虑这个转移。如果有 j1>j2 && dp[ i ][ j1 ]<dp[ i ][ j2 ],则dp[ i ][ j2 ]就是没用的。最后看的是最大的能达到的 j 。

之所以保留那些小的 j ,是因为它们结束时间可能早,可能对后面有利,就是那个dp[ i ][ j ]=dp[ i-1 ][ j-1 ]+len[ i ]的转移。

应该再仔细思考的。只考虑最大的 j ,对它有用的小 j0 其实只有 j0=j-1 。

新来一个建筑,要么是直接从最大的 j 这里变成 j+1 ,要么是继续保持 j 。为了维护 j ,需要 j-1 的值,进而有了第二维。

但其实维护 j 只需要在“继续保持 j ”的时候不要无脑跳过当前建筑,而是替换掉一个耗时更长的建筑,就能维护了!

然后就变成了那种贪心的样子。能修当前建筑就修,不然就换掉一个。

我竟然以为当 now+a[i].len>a[i].t 而又 now-q.top()+a[i].len<=a[i].t 就能说明 a[i].len<q.top()。真是蠢了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=150005;
int n,now;
struct Node{
    int len,t;
}a[N];
priority_queue<int> q;
bool cmp(Node u,Node v){return u.t<v.t;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].len,&a[i].t);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        if(now+a[i].len<=a[i].t)
            now+=a[i].len,q.push(a[i].len);
        else if(q.size()&&a[i].len<q.top()&&now-q.top()+a[i].len<=a[i].t)//a[i].len<q.top()!!!
                now=now-q.top()+a[i].len,q.pop(),q.push(a[i].len);
    printf("%d\n",q.size());
    return 0;
}

 

bzoj 1029 [JSOI2007]建筑抢修——贪心(伪dp)

标签:php   就是   line   namespace   思考   amp   iostream   保留   tar   

原文地址:https://www.cnblogs.com/Narh/p/9366149.html


本文由百家号/熊掌号作者上传并发布,百家号仅提供信息发布平台。文章仅代表作者个人观点,不代表百度立场。

已有 0 条评论

    我有话说: