首页 > 代码库 > HDU 6024 Building Shops
HDU 6024 Building Shops
$dp$。
$dp[i]$表示到$i$位置，且$i$位置建立了的最小花费，那么$dp[i] = min(dp[k]+cost[i+1][k-1])$，$k$是上一个建的位置。最后枚举$dp[i]$，加上最后一段的花费，取个最小值即可。
#include <bits/stdc++.h>using namespace std;const long long mod=1e9+7;const long long inf=1e18;int n;struct X{ long long pos; long long cost;}s[5000];bool cmp(X a,X b){ return a.pos<b.pos;}long long len[5000],dp[5000];int main(){ while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%lld%lld",&s[i].pos,&s[i].cost); } sort(s+1,s+1+n,cmp); len[0]=0; for(int i=1;i<=n;i++) { len[i]=len[i-1]+s[i].pos-s[1].pos; } for(int i=1;i<=n;i++) dp[i]=inf; dp[1]=s[1].cost; for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { if(j==i-1) dp[i]=min(dp[i],dp[j]+s[i].cost); else dp[i]=min(dp[i],s[i].cost+dp[j]+len[i-1]-len[j]-(i-1-j)*(s[j].pos-s[1].pos)); } } long long ans=inf; for(int i=1;i<=n;i++) { if(i==n) ans=min(ans,dp[n]); else ans=min(ans,dp[i]+len[n]-len[i]-(n-i)*(s[i].pos-s[1].pos)); } printf("%lld\n",ans); } return 0;}
HDU 6024 Building Shops
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。