1213.cpp

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

#include<vector>
#include<string>
#include<algorithm>
#include<sstream>
#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int cmp(const int & a,const int & b){
   return a>b;
}
int main(){
  //ifstream cin("in.txt");
  string s;
  int i,k,j,l;
  cout<<"Problem 7 by team x\n";
  while(getline(cin,s)&&s!=""){
      istringstream is(s);
      is>>l>>k;
	  l+=k;
	  vector<int> vec;
	  while(is>>i) vec.push_back(i+k);
      sort(vec.begin(),vec.end(),cmp);
	  //for(i=0;i<vec.size();i++) cout<<vec[i]<<" ";
	  cout<<endl;
	  cout<<"Board length            ="<<setiosflags(ios::right)<<setw(6)<<l-k<<endl;
      cout<<"Saw width               ="<<setiosflags(ios::right)<<setw(6)<<k<<endl;
      k=0;
	  while(vec.size()){
         k+=1;
		 j=0;
		 for(i=0;i<vec.size();i++){
             if(j+vec[i]<=l){
			 j+=vec[i];
			 vec.erase(&vec[i]);
			 i-=1;
			 }
		 }
	  }
	  cout<<"Number of boards needed ="<<setiosflags(ios::right)<<setw(6)<<k<<endl;
  }
  cout<<"End of problem 7 by team x\n";
}