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