【日常学习】【二分】【单调队列优化线性DP】codevs3342 绿色通道题解

ゞ浴缸里的玫瑰 2022-08-09 06:49 163阅读 0赞

题目描述 Description

《思远高考绿色通道》(Green Passage, GP)是唐山一中常用的练习册之一，其题量之大深受lsz等许多oiers的痛恨，其中又以数学绿色通道为最。2007年某月某日，soon-if (数学课代表)，又一次宣布收这本作业，而lsz还一点也没有写……

高二数学《绿色通道》总共有n道题目要写(其实是抄)，编号1..n，抄每道题所花时间不一样，抄第i题要花a\[i\]分钟。由于lsz还要准备NOIP，显然不能成天写绿色通道。lsz决定只用不超过t分钟时间抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。一段连续的空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒。马老师发怒的程度(简称发怒度)等于最长的空题段长度。

现在，lsz想知道他在这t分钟内写哪些题，才能够尽量降低马老师的发怒度。由于lsz很聪明，你只要告诉他发怒度的数值就可以了，不需输出方案。(快乐融化：那么lsz怎么不自己写程序？lsz：我还在抄别的科目的作业……)

输入描述 Input Description

第一行为两个整数n,t，代表共有n道题目，t分钟时间。

以下一行，为n个整数，依次为a\[1\], a\[2\],... a\[n\]，意义如上所述。

输出描述 Output Description

仅一行，一个整数w，为最低的发怒度。

样例输入 Sample Input

17 11

6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

60%数据 n<=2000

100%数据 0<n<=50000，0<a\[i\]<=3000，0<t<=100000000

目测这篇博文之后会比较抢手，因为这道题目没有题解，百度搜索只会出现一个新浪博客，bing也只会搜出五个结果= =

这道题目目前只有codevs tyvj 以及SJTU ACM自己的题库里有···题目来自TSOI2007模拟赛 \[2007-09-08\]

这道题目的出题人（或者补充数据者）简直是良心出题人阿有木有！！！五十个测试点！！！卡标算！！！

由于补充的十几个点会卡掉n²的算法，需要用单调队列优化···

我们首先用二分查找，对于每个mid检查can()函数是否合法，即是否有一种方案满足最长的空题段长度为mid

如何检查呢？

用f\[i\]表示在做第i道题的情况下，前i道题在合法状况下（即空题段长度不超过mid）可能的所有方案中的最小时间（**注意，空题段可能小于mid，这也是合法的**）

那么转移方程为：f\[i\]=min(f\[j\])+a\[i\];

其中j的范围是i-mid-1<=j<=i-1 这是因为我们**保证a\[i\]入选**，且由于最大空时段为mid，枚举j应当从i之前不做mid个的前面那一道题开始

**由于每个f\[j\]内的状态必然是合法的最小值，也就是最长空时段不超过mid的最小值，而j又一定被选中（做这道题），最终方案也一定是合法的。**

如果还不理解，那就纸笔模拟一下吧，样例是很好的。

单调队列由于之前没有相关的博文，算是这个博客中第一次出现，在这里解释下，基本上引用的是一位江苏省队神犇的论文，然而并不知道名字···

例题：一个含有n项的数列(n<=2000000)，求出每一项前面的第m个数到它这个区间内的最小值。

**直接求解的复杂度是O(nm)**

**我们维护这样一个队列：队列中的每个元素有两个域\{position,value\}，分别代表他在原队列中的位置和，我们随时保持这个队列中的元素两个域都单调递增。**

**计算时，只要在队首不断删除，直到队首的position大于等于i-m+1，那此时队首的value必定是f\[i\]，因为队列是单调的！**

**将a\[i\]插入到队列：首先，要保证position单调递增，由于我们动态规划的过程总是由小到大（反之亦然），所以肯定在队尾插入。**

**又因为要保证队列的value单调递增，所以将队尾元素不断删除，直到队尾元素小于a\[i\](由于要求最小值，大的自然用不到)。**

**每个元素最多值入队出队1次，复杂度O(n)**

那么放代码

//codevs3342 绿色通道 二分+单调队列优化DP
    //copyright by ametake
    //thanks to 量子纠缠 from NUST and wu_yihao from CSDN 
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=50000+10;
    int n,t;
    int a[maxn],f[maxn],q[maxn];
    
    
    bool can(int x)
    {
        memset(f,0x3f,sizeof(f));
        f[0]=0;
        int l=0,r=0;
        q[r++]=0;
        for (int i=1;i<=n;i++)
        {
            while (l<=r&&q[l]
          
           =f[i]) r--;//删除队列尾部所有耗时比当前元素大的元素
            q[++r]=i; 
            /*
            //朴素的写法是这样的： 
            for (int j=max(i-x-1,0);j
           
            >1; if (can(mid)) { r=mid; } else l=mid+1; } printf("%d",l); while (1); return 0; }

——旧时茅店社林边，路转溪桥忽见