【题意】：n个教室，选一些教室建造糖果商店。 每个教室，有一个坐标xi和在这个教室建造糖果商店的花费ci。 对于每一个教室，如果这个教室建造糖果商店，花费就是ci,否则就是与坐标在自己前面的建造糖果商店的距离， 求最小花费。
【分析】：
题解1.首先最左面的楼是必须要建商店的。考虑dp，dp[i][j]表示在第i栋楼是否建商店的最小花费（0不建，1建）。
j==1：则dp[i][1]=min(dp[i-1][1],dp[i-1][0]) + 建商店花费;
j==0：则我们找到左面建商店的楼 j，dp[i][0]=dp[j][1] +（j +1至i 楼到 j 栋的花费）。注意位置不是按升序给的，要排个序。
题解2.根据题目所给的时间，和题目的数据的大小，我们可以知道题目可以承受住时间复杂度为O(n^2)。
并且每个教室只有两种方案，要么建超市，要么不建。这就很像是背包问题了，所以我们就想到了dp.
我们设dp[i][0]表示在教室i不建超市时前i个教室的费用和的最小值；dp[i][1]表示在教室i建超市时前i个教室的费用和的最小值
那么我们很快可以得出：
dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + ci
dp[i][0],由于可以承受住时间复杂度为O(n^2)的算法，那么我们就可以想到枚举离教室 i 最近的超市 j 的位置，然后取所有情况的最小值就可以了。
假设左边最近超市为 j ，那么教室 j+1 ~教室i 都不能建超市，所以教室 j+1~教室i 的费用分别为他们的位置到教室j 之间的距离了。
dp[i][0] = dp[j][1] + ( 教室j+1~教室i 的费用 )
如果我们暴力求解，那么时间复杂度会变成O(n^3)，会超时。但是我们会发现由于j是从大到小变化的，所以就可以用：t += (i - j) * (nodes[j+1].x - nodes[j].x);来记录教室j+1~教室i的费用和了。
关于 t += (i - j) * (nodes[j+1].x - nodes[j].x); 的解释：
比如我们要算x3 - x1 ， x2 - x1的sum,那么由于保证了x是升序排列的，所以sum = (x3 - x2) + 2 * (x2 - x1).
【代码】：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<math.h> #include<queue> #include<stack> #include <vector> #include<iostream> using namespace std; #define N 50005 #define INF 0x3f3f3f3f #define LL long long LL dp[N][2]; struct node { LL x,c; }s[N]; int cmp(node a,node b) { return a.x<b.x; } int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%lld %lld",&s[i].x,&s[i].c); sort(s+1,s+n+1,cmp); memset(dp,0,sizeof(dp)); dp[1][1] = s[1].c;///东边肯定有糖果店 所以第一个教室是必须建糖果店的 dp[1][0] = INF; for(int i=2;i<=n;i++) { dp[i][1] = min(dp[i-1][1],dp[i-1][0])+s[i].c; ///在这个教室建立糖果店所需要的最小花费 LL sum=0; dp[i][0] = INF; ///找到前面花费最小的糖果店 for(int j=i-1;j>=1;j--) { sum+=(i-j)*(s[j+1].x-s[j].x); dp[i][0] = min(dp[i][0],dp[j][1]+sum); } } printf("%lld ",min(dp[n][1],dp[n][0])); ///取建糖果店与不建糖果店的其中的小值 } return 0; }