$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+;
const long long inf=1e18;
int n;
struct X
{
long long pos;
long long cost;
}s[]; bool cmp(X a,X b)
{
return a.pos<b.pos;
}
long long len[],dp[]; int main()
{
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++)
{
scanf("%lld%lld",&s[i].pos,&s[i].cost);
}
sort(s+,s++n,cmp);
len[]=;
for(int i=;i<=n;i++)
{
len[i]=len[i-]+s[i].pos-s[].pos;
}
for(int i=;i<=n;i++) dp[i]=inf;
dp[]=s[].cost;
for(int i=;i<=n;i++)
{ for(int j=;j<i;j++)
{
if(j==i-)
dp[i]=min(dp[i],dp[j]+s[i].cost);
else
dp[i]=min(dp[i],s[i].cost+dp[j]+len[i-]-len[j]-(i--j)*(s[j].pos-s[].pos));
}
}
long long ans=inf;
for(int i=;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[].pos));
}
printf("%lld\n",ans);
}
return ;
}
05-11 15:25
查看更多