1245.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int deal(vector<vector<int> > & vec,int x,int y,int n){
   int h=1,d=1;
   while(x-h>=0&&y+h<2*n-1&&vec[x-h][y+h]>=1+2*h) h+=1;
   while(x+d<n&&y+d<2*n-1&&vec[x+d][y+d]>=1+2*d) d+=1;
   if(h>d) return h;
   else return d;
}
int main(){
  ifstream cin("1245.txt");
  int n,i,j,k,max,c=1;
  char input;
  while(cin>>n&&n){
	 vector<int>  temp(2*n-1,0);
	 vector<vector<int>  > vec(n,temp);
	 for(i=0;i<n;i++)
		 for(j=i;j<2*n-i-1;j++){
			cin>>input;
		    if(input=='-') vec[i][j]=1;
		 }
	 for(i=0;i<n;i++){ 
        for(j=1;j<2*n-1;j++){ 
          if(vec[i][j]) vec[i][j]=vec[i][j-1]+1; 
       } 
	 } 
/*	 for(i=0;i<vec.size();i++){
		 for(j=0;j<vec[0].size();j++)
			 cout<<vec[i][j];
		 cout<<endl;
	 }*/
	 max=0;
	 for(i=0;i<n;i++)
		 for(j=0;j<2*n-1;j++)
             if(vec[i][j]){
                k=deal(vec,i,j,n);
				if(k>max) max=k;
			 }
	 cout<<"Triangle #"<<c++<<"\nThe largest triangle area is "<<max*max<<".\n\n";
  }
}