1411ss.cpp

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

#include<vector>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
void set(vector<vector<int> > & map,int i,int j,int w,int h,int n){
     for(int ii=0;ii<h;ii++)
		 for(int jj=0;jj<w;jj++)
			 map[i+ii][j+jj]=1;
}
bool canset(vector<vector<int> > & map,int i,int j,int w,int h,int n){
   if(i+h>n||j+w>n) return false;
   else{
     for(int ii=0;ii<h;ii++)
		 for(int jj=0;jj<w;jj++)
			 if(map[i+ii][j+jj]!=0) return false;
	 return true;
   }
}
void deal(const int & a,vector<int> & cake,vector<vector<int> > map,int d,int & flag,const int & n){
	if(d==a){flag=1;return;}
	else{
        int w=cake[d],h=w;
		//cout<<w<<" "<<h<<endl;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			   if(flag==0&&canset(map,i,j,w,h,n)){
			       vector<vector<int> > copymap=map;
				   set(map,i,j,w,h,n);
				   d+=1;
				   //cout<<"d"<<d<<endl;
				   deal(a,cake,map,d,flag,n);
				   d-=1;
				   if(d<2&&flag==0){flag=2;return;}
				   map=copymap;
			   }
	}
}
int cmp(const int & a,const int & b){
  return a>b;
}
int main(){
  //ifstream cin("1411.txt");
  int n,i,j,k,a,b,t,l;
  cin>>j;
  for(l=0;l<j;l++){
      cin>>n>>t;
	  vector<int> cake(t);k=0;
	  for(i=0;i<t;i++){
         cin>>cake[i];
		 k+=cake[i]*cake[i];
	  }
	  if(k!=n*n) {cout<<"HUTUTU!\n";continue;}
	  vector<int> temp(n,0);
	  vector<vector<int> > vec(n,temp);
      sort(cake.begin(),cake.end(),cmp);
	  a=find(cake.begin(),cake.end(),1)-cake.begin();
	  if(a!=cake.size()) cake.erase(cake.begin()+a,cake.end());
	  a=cake.size();
/*	  if(a==0) {cout<<"KHOOOOB!\n";continue;}
	  vector<int> docake,numcake,abc;
	  for(i=0;i<a;i++)
		  if(!docake.size()||cake[i]!=docake.back()){
              docake.push_back(cake[i]);
			  numcake.push_back(1);
		  }
		  else{
              numcake.back()+=1;
		  }
	  b=0;abc=numcake;*/
	  b=0;
	  deal(a,cake,vec,0,b,n);
      if(b==1)cout<<"KHOOOOB!\n";
	  else cout<<"HUTUTU!\n";
  }
}