1196.cpp

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

#include<iostream>
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
class item{
public:
	int v,id,f;
	item(){f=0;}
};
int cmp1(const item & a,const item & b){
    return a.v>b.v;
}
int cmp2(const item & a,const item & b){
    return a.id<b.id;
}
int deal(const vector<int> & vec,int i,int j){
  int k,l,m=2100000000,r=0;
  for(l=vec[i];l<=vec[j];l++){
     r=0;
	 for(k=i;k<=j;k++){
         r+=abs(vec[k]-l);
	 }
	 if(r<m) m=r;
  }
  return m;
}
int main(){
  //ifstream cin("in.txt");
  int s,i,j,k,n,c=0;
  while(cin>>n>>k&&n!=0){
     vector<int> res(n);
	 vector<item> cha(n);
	 for(i=0;i<n;i++) cin>>res[i];
	 for(i=0;i<n-1;i++) {cha[i].v=res[i+1]-res[i];cha[i].id=i;}
	 cha[n-1].v=2100000000;cha[n-1].id=n-1;
     sort(cha.begin(),cha.end(),cmp1);
	 for(i=0;i<k;i++) cha[i].f=1;
     sort(cha.begin(),cha.end(),cmp2);
	 s=j=0;
	 for(i=0;i<n;i++){
		 if(cha[i].f==1){
             s+=deal(res,j,i);
			 j=i+1;
		 }
	 }
	 cout<<"Chain "<<++c<<"\nTotal distance sum = "<<s<<endl<<endl;
  }
}