【noip2010】 도시 인입(검색+DP)

제목의 뜻

n*m의 격자도를 제시하면 도시를 대표한다. 각 격자마다 수리 시설을 건설하는 데 두 가지 선택이 있다. 1) 첫 번째 줄에 있는 격자에는 저수장 2) 주변에 해발보다 높고 공공 변두리를 가진 수리 시설이 있는 인접 도시가 존재하고 송수장을 건설할 수 있다.n 행위 가뭄 지역을 기록하다.가뭄 지역의 도시로 하여금 모두 수리 시설을 건설할 수 있는지, 만약 할 수 있다면, 최소한 몇 개의 저수장을 건설할 수 있는지, 만약 할 수 없다면, 수리 시설을 건설할 수 없는 도시 수를 구할 수 있는지를 묻는다.

데이터 범위

    n,m<=500

사고의 방향

검색+가지치기+DP는 첫 줄마다 샅샅이 뒤져 검색할 수 있는 가뭄 지역 도시를 표시한다.만약 수색이 끝난 후에도 여전히 가뭄 지역 도시가 표기되지 않았다면, 해답이 없을 것이다.그렇지 않으면 각 지점에서 수색된 가뭄 지역은 반드시 연속적인 구간이 될 것이다.(만약 연속되지 않는 구간이 존재한다면 연속되지 않는 점은 사방의 점에 의해 고립되어 풀리지 않는 상황에 속한다) 그러면 문제는 최소한의 구간으로 선을 덮어쓰는 간단한 DP로 바뀌면 된다.

for(int i = 1; i <= m; ++i)
    for(int j = l[i]; j <= r[i]; ++j)
        f[j] = min(f[j],f[l[i]-1] + 1);

Code

#include
#include
#include

const int sm = 503;
const int sn = 250003;
const int Inf = 0x3f3f3f3f;

int n,m;
int q[sm],h[sm][sm];

struct node {
    int x,y;
}que[sn],t;

struct QJ {
    int l,r;
    bool operator < (const QJ & oth) const {
        return l != oth.l ? l < oth.l : r < oth.r;
    }
}a[sm];

int xx[4] = {-1,1,0,0};
int yy[4] = {0,0,-1,1};

bool ex[sm];
bool vis[sm][sm];

int Max(int x,int y) { return x>y?x:y; }
void Chkmin(int &x,int y) { x = y < x ? y : x; }
void Chkmax(int &x,int y) { x = y > x ? y : x; }

bool chk(int a,int b,int x,int y) {
    if(1<=x&&x<=n&&1<=y&&y<=m) {
        if(h[a][b] > h[x][y]) return true;
    }
    return false;
}

void Bfs(int u,int v) {
    int head = 0, tail = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            vis[i][j] = 0;

    que[++tail] = (node) { u,v };
    vis[u][v] = 1;

    while(head < tail) {
        t = que[++head];
        if(t.x == n) {
            ex[t.y] = 1;
            Chkmin(a[v].l,t.y);
            Chkmax(a[v].r,t.y);
        }
        for(int i = 0; i < 4; ++i)
            if(chk(t.x,t.y,t.x+xx[i],t.y+yy[i]) && !vis[t.x+xx[i]][t.y+yy[i]]) {
                vis[t.x+xx[i]][t.y+yy[i]] = 1;
                que[++tail] = (node) {t.x+xx[i],t.y+yy[i]};
            }
    }
}

int main() {
    freopen("1.in","r",stdin);

    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1;j <= m; ++j)
            scanf("%d",&h[i][j]);
    for(int i = 1; i <= m; ++i) {
        a[i].l = Inf, a[i].r = -1;
        if(h[1][i-1] <= h[1][i] && h[1][i] >= h[1][i+1])
            Bfs(1,i);
    }

    int cnt = 0;
    for(int i = 1; i <= m; ++i)
        if(!ex[i]) ++cnt;

    if(cnt) printf("0
%d
",cnt);
    else {

        std::sort(a+1,a+m+1);

        int k,to, R = 0, ans = 0;
        for(int i = 1; i <= m; ++i) {
            if(a[i].r <= R) continue;
            k = i,to = 0; 
            while(a[k].l <= R+1) 
                to = Max(to,a[k++].r);
            R = to, ans++;
        }
        printf("1
%d
",ans); 
    }
    return 0;
}