记录编号	73511	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2013-10-21 20:24:26	内存使用	1.52 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEN=501,SIZEM=501;
const int INF=0x7fffffff;
int n,m;
int height[SIZEN][SIZEM]={0};
class SEG{
public:
	int l,r;
	SEG(){
		l=INF;
		r=0;
	}
};
bool operator < (SEG a,SEG b){
	return a.r<b.r;
}
SEG line[SIZEN];
void read(void){
	scanf("%d%d",&n,&m);
	int i,j;
	for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&height[i][j]);
}
bool flag[SIZEN][SIZEM]={0};
bool watered[SIZEM]={0};
void floodfill(int s,int x,int y){
	if(x==n){
		watered[y]=true;
		line[s].l=min(line[s].l,y);
		line[s].r=max(line[s].r,y);
	}
	flag[x][y]=true;
	int h=height[x][y];
	if(x<n&&height[x+1][y]<h&&!flag[x+1][y]) floodfill(s,x+1,y);
	if(x>1&&height[x-1][y]<h&&!flag[x-1][y]) floodfill(s,x-1,y);
	if(y<m&&height[x][y+1]<h&&!flag[x][y+1]) floodfill(s,x,y+1);
	if(y>1&&height[x][y-1]<h&&!flag[x][y-1]) floodfill(s,x,y-1);
}
int num_water(void){
	int i,sum=0;
	for(i=1;i<=m;i++) if(watered[i]) sum++;
	return sum;
}
void init(void){
	int i;
	for(i=1;i<=m;i++){
		if(i>1&&height[1][i]<height[1][i-1]) continue;
		if(i<m&&height[1][i]<height[1][i+1]) continue;
		memset(flag,0,sizeof(flag));
		floodfill(i,1,i);
	}
}
int f[SIZEM]={0};
void dp(void){
	int i,j,tot=1;
	for(i=1;i<=m;i++) f[i]=INF/2;
	for(i=1;i<=m;i++){
		if(i<line[tot].r) continue;
		while(tot<=m&&i>line[tot].r) tot++;
		while(i==line[tot].r){
			f[i]=min(f[i],f[line[tot].l-1]+1);
			tot++;
		}
		for(j=1;j<i;j++) f[j]=min(f[j],f[i]);
	}
}
int main(){
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	read();
	init();
	int maxw=num_water();
	if(maxw<m){
		printf("0\n%d\n",m-maxw);
		return 0;
	}
	sort(line+1,line+1+m);
	dp();
	printf("1\n%d\n",f[m]);
	return 0;
}