2017 中国大学生程序设计竞赛女生专场 Building Shops （hdu6024）

Building Shops

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

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

Output

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

Sample Input

1 2

2 3

3 4

1 7

3 1

5 10

6 1

Sample Output

dp[i]代表最后一个商店建在i的最小花费。当前状态是会影响后面的状态的,所以通过前面的状态进行更新是最好的选择.

所以就有dp[i]可以通过比i小的所有方案进行更新

dp[i]=dp[j]+save[i].cost-(n-i+1)*(save[i].pos-save[j].pos);

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1<<28;
const int maxn=3010;
const int maxm=110;
const int mod=1e9+7;
const double pi=acos(-1.0);
ll n;
struct node
{
    ll pos,cost;
    bool friend operator<(node a,node b)
    {
        return a.pos<b.pos;
    }
}save[maxn];
ll dp[maxn];
int main()
{
    //freopen("in1002.txt","r",stdin);
    while(~scanf("%lld",&n))
    {
        for(ll i=1;i<=n;i++)
            scanf("%lld %lld",&save[i].pos,&save[i].cost);
        sort(save+1,save+n+1);
        dp[1]=save[1].cost;
        for(ll i=2;i<=n;i++)
            dp[1]+=(save[i].pos-save[1].pos);
        //dp[i]表示最后一个商店建在i的最小花费
        for(ll i=2;i<=n;i++)
        {
            for(ll j=1;j<i;j++)
            {
                if(j==1)
                dp[i]=dp[j]+save[i].cost-(n-i+1)*(save[i].pos-save[j].pos);
                else
                dp[i]=min(dp[i],dp[j]+save[i].cost-(n-i+1)*(save[i].pos-save[j].pos));
            }
        }
        ll ans=dp[1];
        for(ll i=1;i<=n;i++)
            ans=min(ans,dp[i]);
        printf("%lld
",ans);
    }
    return 0;
}

/***2017.7.11更新***/

前不久学到了斜率优化，今天想起来这题可以用到，结果居然优化到了时间排名第一了，真是惊喜呀！

等有时间再讲讲斜率优化，就先把代码贴出来吧。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define pb push_back
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define cls(name,x) memset(name,x,sizeof(name))
#define pos first
#define cost second
#define mp make_pair
using namespace std;
const int inf=1e9+10;
const ll llinf=1e16+10;
const int maxn=3010;
const int maxm=1e2+10;
const int mod=1e9+7;
int n;
pair<ll,ll> shop[maxn];
ll dp[maxn];
double kfunc(int i,int j)
{
    return ((double)(dp[j]-dp[i]))/(shop[j].pos-shop[i].pos);
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            ll a,b;
            scanf("%lld %lld",&a,&b);
            shop[i]=mp(a,b);
        }
        sort(shop+1,shop+n+1);
        dp[1]=shop[1].cost;
        for(int i=2;i<=n;i++)
            dp[1]+=(shop[i].pos-shop[1].pos);
        dp[2]=dp[1]+shop[2].cost-(n-2+1)*(shop[2].pos-shop[1].pos);
        int Q[maxn];
        int f=0,r=1;
        Q[0]=1;
        Q[1]=2;
        for(int i=3;i<=n;i++)
        {
            while(kfunc(Q[f],Q[f+1])<i-n-1 && r-f+1>2) f++;
            int j;
            if(kfunc(Q[f],Q[f+1])>i-n-1)
                j=Q[f];
            else j=Q[f+1];
            dp[i]=dp[j]+shop[i].cost-(shop[i].pos-shop[j].pos)*(n-i+1);
            if(kfunc(Q[r],i)>kfunc(Q[r-1],Q[r]))
            {
                Q[++r]=i;
            }
            else
            {
                while(r-f+1>1 && kfunc(Q[r],i)<kfunc(Q[r-1],Q[r]) )//可利用短路防止越界报错
                    r--;
                Q[++r]=i;
            }
        }
        ll ans=dp[1];
        for(ll i=1;i<=n;i++)
        {
            ans=min(ans,dp[i]);
        }
        printf("%lld
",ans);
    }
    return 0;
}

2017 中国大学生程序设计竞赛 女生专场 Building Shops （hdu6024）

Building Shops

2017 中国大学生程序设计竞赛女生专场 Building Shops （hdu6024）