2016年1月16日 星期六

[HOJ 297][NOIP 2010 提高組]引水入城

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

這題看似簡單,但要想出時間複雜度夠低的做法不太容易
我們可以考慮一個DP[i][j]存二元組(l,r)代表(i,j)這個點最左邊能夠到達第l行的水庫,最右邊能夠到達第r行的水庫,如果這個點無法到達任何水庫,則(l,r)=(INF,-INF)

經過觀察,可以發現,對於任何兩個沙漠城市a,b(a在b的左邊),如果a能夠到達最右邊的水庫的位置>=b能夠到達最左邊的水庫的位置,那麼a和b的這兩條水路一定會有交叉,換句話說,a和b可以共用同一個水庫!

反之,則a和b無法共用相同的水源

因此,我們只要求出所有的DP[N][i],1<=i<=M,就可以透過一個貪心策略,將i從1到M跑一次,如果一個點(N,i)可以到達最左邊的水庫的位置>目前啟用最右邊的水庫的位置,就把這點能夠到達最右邊的水庫啟用

這樣,如果中途出現DP[N][i]=(INF,-INF),就改為計算幾個點也是(INF,-INF),代表有幾座乾旱區中的城市不可能建有水利設施,不然的話,依照上述策略啟用了幾座水庫就代表最少建造幾個蓄水廠

再來就是DP怎麼算了

首先,因為旁邊的高度要嚴格小於這裡的高度水才會流過去,因此不會有環狀鬆弛的問題,因此對於每個DP[i][j],可以用DP[y][x]來更新,其中(y,x)必須在(i,j)旁邊且高度比(i,j)還高
這裡使用記憶化搜索較為方便,注意在到達河邊的時候DP的初始值要設為(c,c)而不是(INF,-INF)

時間複雜度O(N*M)


code:
#include<cstdio>
#include<cassert>
using namespace std;
const int INF=2147483647;
void getmin(int &a,const int b){if(b<a)a=b;}
void getmax(int &a,const int b){if(b>a)a=b;}
struct Span
{
    int l,r;
    Span(){}
    Span(const int _l,const int _r):l(_l),r(_r){}
}SPAN[500][500];
int N,M,H[500][500];
Span GetSPAN(const int r,const int c,const int h)
{
    if(r<0||c<0||r>=N||c>=M||H[r][c]<=h)return Span(INF,-INF);
    Span &ans=SPAN[r][c];
    if(ans.l!=-1)return ans;
    ans=(r==0?Span(c,c):Span(INF,-INF));
    static int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
    for(int i=0;i<4;i++)
    {
        const Span tmp=GetSPAN(r+d[i][0],c+d[i][1],H[r][c]);
        getmin(ans.l,tmp.l),getmax(ans.r,tmp.r);
    }
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)for(int j=0;j<M;j++)scanf("%d",&H[i][j]),SPAN[i][j]=Span(-1,-1);
        int reservoir=0,drought=0,mxr=-1;
        for(int i=0;i<M;i++)
        {
            const Span s=GetSPAN(N-1,i,-INF);
//            printf("(%d,%d)\n",s.l,s.r);
            if(s.l==INF)drought++;
            else if(drought==0&&s.l>mxr)reservoir++,mxr=s.r;
        }
        if(drought>0)printf("0\n%d\n",drought);
        else printf("1\n%d\n",reservoir);
        break;
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原