【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;

}

巴特西

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

最新文章

热门文章