hdoj 6024 Building Shops

Problem Description

HDU’s

Input
The input contains several test cases, no more than 10 test cases.
In each test case, the first line contains an integer n(1≤n≤3000), denoting the number of the classrooms.
In the following n lines, each line contains two integers xi,ci(−109≤xi,ci≤109), denoting the coordinate of the i-th classroom and the cost of building a candy shop in it.
There are no two classrooms having same coordinate.

Output

For each test case, print a single line containing an integer, denoting the minimal cost.

Sample Input

Sample Output

5
11

参考了http://blog.csdn.net/STILLxjy/article/details/72514980

题意：题意有点坑，总让我觉得这是国人写的英文版，

x轴上有n个班级主要问题就是建与不建，就是0和1的问题，即dp ，问总费用最少为多少

1：在第i个教室建超市，费用因为ci
2：没有建超市的教室的费5用为它和它左边最接近的超市的坐标之间的距离

我们设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],我们可以想到枚举离教室i最近的超市j的位置，然后取所有情况的最小值就可以了。

关于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 mp+= (i - j) * dp[j+1].x - dp[j].x);来记录教室j+1~教室i的费用和了。

关于 tmp += (i - j) * (dp[j+1].x - dp[j].x); 的解释：
比如我们要算x3 - x1 ， x2 - x1的sum,那么由于保证了x是升序排列的，所以sum = (x3 - x2) + 2 * (x2 - x1).

AC代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef  long long ll;
 6 const int maxn =3030;
 7 ll dp[maxn][maxn]={0};
 8 struct classroom{
 9     int x,c;
10 }a[maxn];
11 int cmp(classroom xx,classroom yy){
12     return xx.x<yy.x; //升序排列
13 }
14 int main(){
15     int n;
16     while(~scanf("%d",&n)){
17         for(int i=1;i<=n;i++)
18             scanf("%d%d",&a[i].x,&a[i].c);
19         sort(a+1,a+n+1,cmp);
20         dp[1][0]=(ll)1<<60;
21         dp[1][1]=a[1].c;
22         for(int i=2;i<=n;i++){
23             dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i].c;
24             ll tmp=0;
25             dp[i][0]=(ll)1<<60;
26             for(int j=i-1;j>0;j--){
27                 tmp=(ll)(a[j+1].x-a[j].x)*(i-j)+tmp;
28                 dp[i][0]=min(dp[i][0],dp[j][1]+tmp);
29             }
30         }
31         printf("%lld
",min(dp[n][0],dp[n][1]));
32     }
33     return 0;
34 }
35 /*     <<
36  1的2进制是
37 000…0001
38 (这里前面0的个数和int的位数有关，32位机器，gcc里有31个0)，左移2位之后变成:
39 000…0100,
40 也就是10进制的4，所以说左移1位相对于乘以2的n次方
41  */