[USACO 2010 Nov G]Buying Feed

Consider this example where FJ needs two pounds of feed which he must purchase from some of the three stores at locations 1, 3, and 4 on a number line whose range is 0..5: 0 1 2 3 4 5 X +---|---+---|---|---+ 1 1 1 Available pounds of feed 1 2 2 Cents per pound It is most economical for FJ to buy one pound of feed from both the second and third stores. He must pay two cents to buy each pound of feed for a total cost of 4. FJ's driving from location 0 to location 3 costs nothing, since he is carrying no feed. When FJ travels from 3 to 4 he moves 1 mile with 1 pound of feed, so he must pay 1*1*1 = 1 cents. When FJ travels from 4 to 5 he moves one mile with 2 pounds of feed, so he must pay 1*2*2 = 4 cents. His feed cost is 2 + 2 cents; his travel cost is 1 + 4 cents. The total cost is 2 + 2 + 1 + 4 = 9 cents.

C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 592K, 提交时间: 2019-11-30 11:53:23

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#include<algorithm>
using namespace std;
int n,m,e,q[10500],he,ta;//q[600]!!!!!!!!
struct nod{
	int x,c;
	long long v;
	inline bool operator <(const nod &b)const{
		return x<b.x;
	}
}a[600];
long long f[2][10100],oo,p[10500];
int main(){
	scanf("%d%d%d",&m,&e,&n);
	fo(i,1,n) scanf("%d%d%lld",&a[i].x,&a[i].c,&a[i].v);
	sort(a+1,a+n+1);
	a[++n].x=e;
	oo=0x3fffffff;
	oo*=oo;
	fo(i,1,m) f[1][i]=oo;
	//f[i][j]=min{f[i-1][k]+v[i-1]*(j-k)+j*j*(x[i]-x[i-1])}
	//f[i][j]=min{f[i-1][k]-v[i-1]*k}+v[i-1]*j+j*j*(x[i]-x[i-1])
	fo(i,2,n){
		he=1;ta=0;
		fo(j,0,m){
			p[j]=f[(i&1)^1][j]-a[i-1].v*j;
			while (he<=ta&&p[j]<p[q[ta]]) ta--;
			q[++ta]=j;
			if (j-q[he]>a[i-1].c) he++;
			f[i&1][j]=p[q[he]]+a[i-1].v*j+j*j*(a[i].x-a[i-1].x);
		}
	}
	printf("%lld\n",f[n&1][m]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 128ms, 内存消耗: 488K, 提交时间: 2020-04-03 09:12:23

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

详情