【luoguP4544】[USACO10NOV]购买饲料Buying Feed

题目链接

首先把商店按坐标排序

\(dp_{i,j}\)表示前i个商店买了j吨饲料并运到终点的花费，二进制拆分优化转移

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;const int N=10010;int n,E,K,dp[N];
struct Data{
int x,f,c;
} a[N];inline bool cmp(Data p,Data q){
return p.x<q.x;
}signed main()
{
scanf("%lld%lld%lld",&K,&E,&n);
for(int i=1;i<=n;++i)
scanf("%lld%lld%lld",&a[i].x,&a[i].f,&a[i].c);
sort(a+1,a+1+n,cmp);
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;++i){
int sum=0;
for(int k=1;sum+k<=a[i].f;k<<=1){
sum+=k;
for(int j=K;j>=k;--j)
dp[j]=min(dp[j],dp[j-k]+a[i].c*k+(j*j-(j-k)*(j-k))*(E-a[i].x));
}
int k=a[i].f-sum;
for(int j=K;j>=k;--j)
dp[j]=min(dp[j],dp[j-k]+a[i].c*k+(j*j-(j-k)*(j-k))*(E-a[i].x));
}
printf("%lld\n",dp[K]);
return 0;
}