【题意】：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][];
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=;i<=n;i++)
scanf("%lld %lld",&s[i].x,&s[i].c);
sort(s+,s+n+,cmp);
memset(dp,,sizeof(dp));
dp[][] = s[].c;///东边肯定有糖果店 所以第一个教室是必须建糖果店的
dp[][] = INF;
for(int i=;i<=n;i++)
{
dp[i][] = min(dp[i-][],dp[i-][])+s[i].c;
///在这个教室建立糖果店所需要的最小花费
LL sum=;
dp[i][] = INF;
///找到前面花费最小的糖果店
for(int j=i-;j>=;j--)
{
sum+=(i-j)*(s[j+].x-s[j].x);
dp[i][] = min(dp[i][],dp[j][]+sum);
}
}
printf("%lld\n",min(dp[n][],dp[n][]));
///取建糖果店与不建糖果店的其中的小值
}
return ;
}
还很鶸阿
