[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;
}