HDU6024：Building Shops（DP）

传送门

题意

在一条直线上有n个教室，现在要设置糖果店，使得最后成本最小，满足以下两个条件：

1.若该点为糖果店，费用为cost[i];

2.若不是，则为loc[i]-最近的糖果店的loc

分析

dp方程不好想，我们观察一下，如果在第i个点设置最后一个糖果店，那么它将影响到它之前的糖果店，那么第i个点的费用必然由前i-1个的位置上费用最小的糖果店转移过来，这里糖果店费用计算为$cost[i]+\sum_{j=i+1}^n(dis[j]-dis[i])$,那么转移方程为$$dp[i]=dp[j]+cost[i]-(n-i+1)*(dis[i]-dis[j])$$

最后取dp[1~n]其中最小的即可

trick

1.注意爆int

2.注意dp{1]的计算

3.注意位置的排序

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

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

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int n;

struct node

{

    ll loc,cost;

    bool operator<(const node &p)const

    {

        return loc<p.loc;

    }

}a[3030];

ll dp[3030];

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        mem(dp,0);

        for(int i=1;i<=n;++i) scanf("%lld %lld",&a[i].loc,&a[i].cost);

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

        dp[1]=a[1].cost;

        F(i,2,n) dp[1]+=a[i].loc-a[1].loc;

        F(i,2,n)

        {

            dp[i]=1e18;

            F(j,1,i-1)

            {

                dp[i]=min(dp[i],a[i].cost+dp[j]-(n-i+1)*(a[i].loc-a[j].loc));

            }

        }

        //F(i,1,n) printf("%lld\n",dp[i]);

        ll ans=2e9;

        F(i,1,n)

        {

            ans=min(ans,dp[i]);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

HDU6024：Building Shops（DP）

传送门

题意

分析

trick

代码

最新文章

热门文章