1501.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
#include<cmath>
using namespace std;
int main(){
  //ifstream cin("1501.txt");
  int n,i,j,k,aaa=0;
  while(cin>>n&&n){
	 if(aaa) cout<<endl;
	 aaa=1;
     vector<vector<int> > vec;
	 vector<int> temp;
	 vector<int> max(pow(2,n),0),min(pow(2,n),0);
	 for(i=0;i<pow(2,n);i++)
		 temp.push_back(i+1);
	 vec.push_back(temp);
	 for(j=n-1;j>=0;j--){
         temp.resize(pow(2,j));
		 for(i=0;i<pow(2,j);i++)
			 cin>>temp[i];
         vec.push_back(temp);
	 }
	 max[vec[n][0]-1]=1;
     for(i=n-1;i>=0;i--){
        for(j=0;j<vec[i].size();j++)
			if(max[vec[i][j]-1]==0) max[vec[i][j]-1]=max[vec[i+1][j/2]-1]+1; 
	 }
/*     for(i=n-1;i>=0;i--){
        for(j=0;j<vec[i].size();j++)
			if(min[vec[i][j]-1]==0) min[vec[i][j]-1]=pow(2,n)-i; 
	 }*/
	 for(i=1;i<=n;i++)
		 for(j=0;j<vec[i].size();j++)
			 min[vec[i][j]-1]=min[vec[i-1][j*2]-1]+min[vec[i-1][j*2+1]-1]+1;
	 for(i=0;i<min.size();i++)
		 min[i]=pow(2,n)-min[i];
/*     for(i=0;i<max.size();i++)
		 cout<<max[i]<<" ";
	 cout<<endl;
	 for(i=0;i<min.size();i++)
		 cout<<min[i]<<" ";
	 cout<<endl;*/
	 cin>>k;
	 for(i=0;i<k;i++){
		 cin>>j;
		 cout<<"Player "<<j<<" can be ranked as high as "<<max[j-1]<<" or as low as "<<min[j-1]<<".\n";
	 }
     
  }
}