1283.cpp

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

#include<iostream>
#include<fstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<algorithm>
using namespace std;
void round(double & a){
   double b=a*10;
   b=(int) b;
   if((a-b/10)<0.05) a=b/10;
   else a=(b+1)/10;
}
class item{
public:
	vector<double> fenshu;
	double av,aav,g,ag;
	int a,b;
	item(){}
	double makeav(){
        if(fenshu.size()==1) av=fenshu[0];
		else if(fenshu.size()==2) av=(fenshu[0]+fenshu[1])/2;
		else {
           av=-(*min_element(fenshu.begin(),fenshu.end()));
		   for(int i=0;i<fenshu.size();i++){
               av+=fenshu[i];
		   }
		   av/=(fenshu.size()-1);
		}
		round(av);
		return av;
	}
	void makeaav(){
        int incrate=b/2*3;
		aav=av+incrate;
	}
	void makeg(double sd,double pin){
        if(aav>=sd+pin) g=4;
		else if(aav>=pin) g=3;
		else if(aav>=pin-sd) g=2;
		else g=1;
	}
	double makeag(){
        if(a==0){
			ag=g+1;
		    if(ag>4) ag=4;
		}
		else{
			int dec=a/4;
		    ag=g-dec;
		    if(ag<0) ag=0;
		}
		return ag;
	}
};
double makesd(vector<item> & vec,double temp){
    double res=0;
	for(int i=0;i<vec.size();i++){
       res+=(vec[i].av-temp)*(vec[i].av-temp);
	}
	//cout<<"res"<<" "<<res<<endl;
	res/=vec.size();
	res=sqrt(res);
	round(res);
	if(res<1) res=1;
	return res;
}
int main(){
  //ifstream cin("in.txt");
  int c,i,l,r,t,j,k;
  double temp,sd,g;
  cout<<"MAKING THE GRADE OUTPUT\n";
  cin>>c;
  for(l=0;l<c;l++){
      cin>>r>>t; temp=0;
      vector<item> vec(r);
	  for(i=0;i<r;i++){
		  vec[i].fenshu.resize(t);
		  for(j=0;j<t;j++) cin>>vec[i].fenshu[j];
		  cin>>vec[i].b>>vec[i].a;
		  temp+=vec[i].makeav();
		  vec[i].makeaav();
	  }
	  temp/=r; round(temp); sd=makesd(vec,temp);
	  g=0;
	  for(i=0;i<vec.size();i++){
          vec[i].makeg(sd,temp);
          g+=vec[i].makeag();
	  }
	  g/=vec.size();
	  round(g);
	 // for(i=0;i<vec.size();i++){
	 //	  cout<<vec[i].av<<" "<<vec[i].aav<<" "<<vec[i].g<<" "<<vec[i].ag<<" ";
	 // }
	 //cout<<endl;
	  cout<<setiosflags(ios::fixed)<<setprecision(1)<<g<<endl;
  }
  cout<<"END OF OUTPUT\n";
  return 0;
}