题意：输入n，代表n个教室，然后输入每个教室的坐标和建立糖果屋的代价，如果不建立，则代价为和左边第一个糖果屋的距离，第一个教室必须为糖果屋，求最小代价
思路：DP，dp1[i]表示当前我建立的最小值，dp2[i]表示我不建立的最小值.那么dp1[i]=min(dp1[i-1],dp2[i-1])+代价，dp2[i]为dp1[j]+(i与j的距离)，其中j与i之间的教室与j的距离也要算入.
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll dp1[3002]; 5 ll dp2[3002]; 6 struct node{ 7 ll a,b; 8 }x[3004]; 9 ll c[3002]; 10 11 bool cmp(node p,node q){ 12 return p.a<q.a; 13 } 14 int main(){ 15 int n; 16 ll s,ss; 17 ll Min; 18 while(scanf("%d",&n)!=EOF) 19 { 20 memset(dp1,0,sizeof(dp1)); 21 memset(dp2,0,sizeof(dp2)); 22 for(int i=1;i<=n;i++) { 23 scanf("%I64d%I64d",&x[i].a,&x[i].b); 24 } 25 sort(x+1,x+1+n,cmp); 26 c[0]=0; 27 int k; 28 for(int i=1;i<=n;i++) c[i]=c[i-1]+x[i].a; 29 dp1[1]=x[1].b;//建立 30 dp2[1]=x[1].b;//不建立 31 for(int i=2;i<=n;i++){ 32 dp1[i]=min(dp1[i-1],dp2[i-1])+x[i].b; 33 dp2[i]=dp1[i-1]+x[i].a-x[i-1].a; 34 ss=x[i].a-x[i-1].a; 35 k=1; 36 for(int j=i-2;j>=1;j--){ 37 ss+=(x[j+1].a-x[j].a)*(++k); 38 dp2[i]=min(dp2[i],dp1[j]+ss); 39 } 40 // cout<<dp1[i]<<" "<<dp2[i]<<endl; 41 } 42 cout<<min(dp1[n],dp2[n])<<endl; 43 } 44 return 0; 45 }
原文：http://www.cnblogs.com/hhxj/p/6953378.html