2017中国大学生程序设计竞赛

B HDU - 6024

【题意】：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 ;

}

还很鶸阿

巴特西

2017中国大学生程序设计竞赛 - 女生专场B【DP】

最新文章

热门文章