usaco_5_3_4_bigbrn-dp统计大正方形里面最大的小正方形边长.cpp

usaco自己做的1到5章的代码

/*
PROB: bigbrn
LANG: C++
*/
/*
动归题，很像之前第三章的一个题，统计大正方形里面最大的小正方形边长。
rect[i][j]=min{rect[i-1][j],rect[i][j-1],rect[i-1][j-1]}+1;
边界条件：[0,i]没有障碍则rect[0][i]=1，否则rect[0][i]=0 ,i=0..n-1
          [i,0]没有障碍则rect[i][0]=1，否则rect[i][0]=0 ,i=0..n-1
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<cmath>
#include<algorithm>
#include<iomanip>
//#define cin fin
using namespace std;
bool map[1000][1000];
int rect[1000][1000];
int n,t,maxlen;
inline int minf(int a,int b,int c)
{
    int t=a;
    if(t>b) t=b;
    if(t>c) t=c;
    return t;
}
int main()
{
	ifstream fin("bigbrn.in");
	ofstream fout("bigbrn.out");
    int i,j,k,des;
    memset(map,true,sizeof(map));
    maxlen=0;
    fin>>n>>t;
    for(i=0;i<t;i++)
    {
        fin>>j>>k;
        j--;
        k--;
        map[j][k]=false;
        rect[j][k]=0;
    }
    /*for(i=0;i<n;i++){
        for(j=0;j<n;j++)
        fout<<map[i][j];
        fout<<endl;
    }*/
    for(i=0;i<n;i++) {
        if(map[0][i])
            {rect[0][i]=1; maxlen=1;}
        else rect[0][i]=0;
        if(map[i][0])
            {rect[i][0]=1;;maxlen=1;}
        else rect[i][0]=0;
    }

    for(i=1;i<n;i++)
        for(j=1;j<n;j++)
        {
            if(!map[i][j]) continue;
            rect[i][j]=minf(rect[i-1][j],rect[i-1][j-1],rect[i][j-1])+1;
            if(rect[i][j]>maxlen) maxlen=rect[i][j];
        }
    fout<<maxlen<<endl;
	return 0;
}