1411.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(int a,vector<int> & docake,vector<int> numcake,const vector<int> & numcakecopy,vector<vector<int> > map,int d,int p,int & flag,const int & n){
    //cout<<d<<" "<<p<<endl;
	if(d==a){flag=1;return;}
	else if(p==numcake.size()) return;
	else{
        int w=docake[p],h=w;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			   if(!flag&&canset(map,i,j,w,h,n)){
			       vector<vector<int> > copymap=map;
				   set(map,i,j,w,h,n);
				   d+=1;numcake[p]-=1;if(numcake[p]==0) p+=1; 
				   deal(a,docake,numcake,numcakecopy,map,d,p,flag,n);
				   //if(flag!=0) return;
				   else{
				   d-=1;if(p==numcake.size()||numcake[p]==numcakecopy[p]) {p-=1;numcake[p]+=1;}
				   map=copymap;
				   }
			   }
			   else return;
	}
}
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,k=-1;i<a;i++)
		  if(!docake.size()||cake[i]!=docake.back()){
              docake.push_back(cake[i]);
			  numcake.push_back(1);
			  k+=1;
		  }
		  else{
              numcake[k]+=1;
		  }
	  b=0;abc=numcake;
	  deal(a,docake,numcake,abc,vec,0,0,b,n);
      if(b==1)cout<<"KHOOOOB!\n";
	  else cout<<"HUTUTU!\n";
  }
}