Home > Old Blog Posts > USACO 5.3.4 Big Barn

USACO 5.3.4 Big Barn


这题直接把3.3.4的方程套过来就行了……

f[i][j] = 0                    !a[i][j]

min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1 a[i][j]

/*
ID: dementr1
PROG: bigbrn
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("bigbrn.in");
ofstream fout("bigbrn.out");
int n,t,f[1000][1000]={};
bool v[1000][1000];
void init()
{
	int i,j,a,b;
	fin>>n>>t;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			v[i][j]=true;
	for(i=0;i>a>>b;
		v[a-1][b-1]=false;
	}
	fin.close();
}
void work()
{
	int i,j,max=0;
	for(i=0;i<n;i++)
	{
		if(v[0][i])
		{
			f[0][i]=1;
			max=1;
		}
		if(v[i][0])
		{
			f[i][0]=1;
			max=1;
		}
	}
	for(i=1;i<n;i++)
		for(j=1;j<n;j++)
		{
			if(v[i][j])
				f[i][j]=1;
			if(v[i][j])
			{int tmp=f[i-1][j];

			if(f[i-1][j-1]<tmp)
				tmp=f[i-1][j-1];
			if(f[i][j-1]f[i][j])
				f[i][j]=tmp+1;}
			if(f[i][j]>max)
				max=f[i][j];
		}
	fout<<max<<endl;
}
int main()
{
	init();
	work();
	return 0;
}
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: