codevs 3342 綠色通道

codevs 3342 綠色通道

http://codevs.cn/problem/3342/

難度等級：黃金

題目描述 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

3

資料範圍及提示 Data Size & Hint

60%資料 n<=2000

100%資料 0<n<=50000，0<a[i]<=3000，0<t<=100000000

 最小化最大值——二分

很明顯的一個DP

每次二分最長空題段，判斷mid

方法一：樸素的DP

令f[i]表示抄第i道題所花費的最小時間

狀态轉移方程：f[i]=min(f[j])+time[i]    max(0,i-mid-1)<=j<=i-1

初始化:f數組極大值，f[0]=0

時間複雜度：n²

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50001
using namespace std;
int n,t,l,r,mid,ans,f[N],a[N];
inline bool check(int k)
{
    memset(f,127,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
     for(int j=max(i-k-1,0);j<i;j++)
      f[i]=min(f[i],f[j]+a[i]);
    int tmp=0x7fffffff;
    for(int i=n-k;i<=n;i++) tmp=min(tmp,f[i]);
    if(tmp<=t) return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    l=0,r=n;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) {ans=mid;r=mid-1;}
        else l=mid+1;
    }
    printf("%d",ans);
}      

View Code

結果：

方法二：線段樹優化DP

用線段樹維護區間最小值，就可以直接查詢[i-mid-1,i-1]内的最小值

時間複雜度：log n （二分）*n（枚舉每道題）*（log n+log n）（區間查詢+單點修改）= 2*n*log²n

#include<cstdio>
#include<algorithm>
#define N 50001
#define INF 100000010
using namespace std;
int n,t,ql,qr,mid,ans,f[N],a[N];
struct node{int l,r,key;}tr[N*4];
inline int read()//讀入優化 
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x;
}
inline void begin(int k,int l,int r)//初始化 
{
    tr[k].key=INF;
    if(l==r) return;
    int mid=l+r>>1;
    begin(k<<1,l,mid);
    begin((k<<1)+1,mid+1,r);
}
inline int query(int k,int opl,int opr)//區間查詢 
{
    if(tr[k].l>=opl&&tr[k].r<=opr) return tr[k].key;
    int mid=tr[k].l+tr[k].r>>1;
    {
        int ll=INF;if(opl<=mid) ll=query(k<<1,opl,opr);
        int rr=INF;if(opr>mid) rr=query((k<<1)+1,opl,opr);
        return min(ll,rr);
    }    
}
inline void change(int k,int x,int y)//單點修改 
{
    if(tr[k].l==tr[k].r) {tr[k].key=min(tr[k].key,y);return;}
    int mid=tr[k].l+tr[k].r>>1;
    if(x<=mid) change(k<<1,x,y);
    else change((k<<1)+1,x,y);
    tr[k].key=min(tr[k<<1].key,tr[(k<<1)+1].key);
}
inline bool check(int k)
{
    begin(1,0,n);
    change(1,0,0);
    for(int i=1;i<=n;i++) 
    {
        int p=query(1,max(0,i-k-1),i-1);
        change(1,i,p+a[i]);
    }
    int tmp=0x7fffffff;
    if(query(1,n-k,n)<=t) return true;
    return false;
}
inline void build(int k,int l,int r)//建樹 
{
    tr[k].l=l;tr[k].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build((k<<1)+1,mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,0,n);
    ql=0,qr=n;
    while(ql<=qr)
    {
        mid=ql+qr>>1;
        if(check(mid)) {ans=mid;qr=mid-1;}
        else ql=mid+1;
    }
    printf("%d",ans);
}      

方法三：單調隊列優化DP

假設有一段長度為mid的滑動視窗，每次這個視窗可以框住長為mid的一段數

我們需要的是長為mid的一段數裡最小的那一個，是以可以維護一個單調上升的隊列，這樣每次直接取出隊首就好了。

為什麼要維護單調遞增的隊列?

因為如果這個數比前一個大，當視窗移過前一個數時，這個數可能成為最小的

如果這個數比前一個小，這個數的前一個一定不如這個優，是以删去大的

是以這就需要維護2個數組，1個存儲隊列中元素的在原序列中的位置（即第幾道題），1個存儲所需時間

如何維護這個隊列的單調性？

1、數必須在視窗範圍内，假設目前要計算第i個，那麼可以更新它的範圍是[i-mid-1,i-1]，是以如果目前隊首位置<i-mid-1，就讓其出隊

2、單調遞增，如果第抄第i-1道題所需時間比目前的隊尾時間少，就讓隊尾出隊

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50001
using namespace std;
int n,t,head,tail,a[N],f[N],q[N],id[N],l,r,mid,ans;
//a存儲抄每道題所需時間，f抄第i道題的最少時間，q單調隊列數組，存儲所需時間，id單調隊列數組，存儲題目編号 
inline bool check(int k)
{
    memset(q,0,sizeof(q));
    memset(f,0,sizeof(f));
    memset(id,0,sizeof(id));
    head=tail=0;
//隊列采取左閉右開式，有效範圍為[head,tail-1] 
    for(int i=1;i<=n;i++)
    {
        while(id[head]<i-k-1&&head<tail)  head++;//隊首題目編号不在可以更新i的範圍内，出隊 
        while(f[i-1]<q[tail-1]&&head<tail) tail--;//不滿足單調性，出隊 
        q[tail]=f[i-1];//入隊 
        id[tail]=i-1;
        tail++;
        f[i]=q[head]+a[i];
    }
    int tmp=0x7fffffff;
    for(int i=n-k;i<=n;i++) tmp=min(tmp,f[i]);
    if(tmp<=t) return true;
    return false; 
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    l=0,r=n;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) {ans=mid;r=mid-1;}
        else l=mid+1;
    } 
    printf("%d",ans);
}       

作者：xxy

本文版權歸作者所有，轉載請用連結，請勿原文轉載，Thanks♪(･ω･)ﾉ。