HDU 6024 Building Shops （简单dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6024

题意：有n个room在一条直线上，需要这这些room里面建造商店，如果第i个room建造，则要总花费加上C ， 不建造的话， 总花费就要加上去左边的第一间商店的距离。求总的最小花费。

题解：dp1[i] 为第i个建造的最小花费， dp2[i] 为第i个不建造的最小花费。

　　　dp1[i] = min(dp1[i-1], dp2[i-1]) + C

　　　dp2[i] = min(dp2[i], dp1[j] + dis[j][i])  j为[1, i-1]。

　　　j为左手边第一间商店，那么从j到i都是不建商店的，就需要加上 每一间room到商店的距离。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <cmath>

 #include <set>

 using namespace std;

 typedef long long LL;

 #define ms(a, b) memset(a, b, sizeof(a))

 #define pb push_back

 #define mp make_pair

 const int INF = 0x7fffffff;

 const int inf = 0x3f3f3f3f;

 const int mod = 1e9+;

 const int maxn =  + ;

 struct node

 {

     LL x, c;

 };

 LL dp1[maxn];

 LL dp2[maxn];

 LL dis[maxn][maxn];

 void init() {

     ms(dp1, );

     ms(dp2, );

     ms(dis, );

 }

 bool cmp(node x1, node x2)

 {

     return x1.x < x2.x;

 }

 void solve(int n) {

     node a[maxn];

     for(int i=;i<=n;i++)

         scanf("%lld%lld", &a[i].x, &a[i].c);

     for(int i=;i<=n;i++)

         a[i].x+=;

     sort(a+, a+n+, cmp);

     for(int i = ;i<=n;i++){

         for(int j = i+;j<=n;j++){

             dis[i][j] = dis[i][j-] + (a[j].x - a[i].x);

         }

     }

     dp1[] = a[].c;

     dp2[] = a[].c;

     for(int i = ;i<=n;i++){

         dp1[i] = min(dp1[i-], dp2[i-]) + a[i].c;

         dp2[i] = dp1[i];

         for(int j = i-;j>=;j--){

             dp2[i] = min(dp2[i], dp1[j]+dis[j][i]);

         }

     }

     printf("%lld\n", min(dp1[n], dp2[n]));

 }

 int main() {

 #ifdef LOCAL

     freopen("input.txt", "r", stdin);

 //        freopen("output.txt", "w", stdout);

 #endif

     int n;

     while(~scanf("%d", &n)){

         init();

         solve(n);

     }

     return ;

 }