首页 > 分享 > usaco 购买饲料 && 修剪草坪

usaco 购买饲料 && 修剪草坪

花匠小妙招
2024-11-23 13:43

购买饲料

Description

如约翰在镇上，沿着公路开车回家，他的家离起点有E公里。他顺便准备买K吨饲料回家。运送饲料是要花油钱的，如果他的车上有X吨饲料，行驶一公里需要X^2元，行驶D公里就需要DX^2元。约翰可以从N家商店购买饲料，所有商店都在公路边上，第i家店距离起点Xi公里，饲料单价为每吨Ci元，库存为Fi吨。

约翰可以选择在任意商店里购买任意多的饲料，只要那家店的还有货就可以了。保证所有商店的饲料库存之和不会少于K，为了带K吨饲料回家，约翰最少的花费是多少呢？

举个例子，假设有三家商店，情况如下所示：

坐标 X = 1 X = 3 X = 4 E = 5 库存 1 1 1 单价 1 2 2

如果约翰要买2吨饲料回家，那么他的最好选择是在离家较近的两家商店购买饲料，则花在路上的钱是1 + 4 = 5，花在商店的钱是2 + 2 = 4，共需要9元。

Input Format

第一行：三个用空格分开的整数：K，E和N，1 ≤ K ≤ 10000，1 ≤ E,N ≤ 500

第二行到N + 1行：第i + 1行有三个用空格分开的整数一个整数： Xi， Fi和Ci， 0 < Xi < E， 1 ≤ Fi ≤ 10000，1 ≤ Ci ≤ 10,000,000

Output Format

第一行：单个整数，表示约翰购买和运送饲料的最小花费

--------------------------------------------------------------

正解=动归+队列优化

先考虑无优化的Dp

状态：f[i][j] 表示在 i 这个位置且车上有 j 吨饲料至少要多少钱

转移: f[i+1][j]=f[i][j-g]+C[i]*g+j*j*( X[i+1]-X[i] )( 0<=g<=F[i] )

输出：f[n+1][k](设n+1为家)

显然O（N*K*F）必然会TLE

考虑优化

设 g‘=j-g 则 j-g’=g( 0<=g<=F[i] ),

g 增加，g‘ 减少，

则上面的 f[i+1][j] 可表示成

f[i+1][j]=f[i][ g’ ]+C[i]*( j-g' )+j*j*( X[i+1]-X[i])

=f[i][ g’ ]+ C[i]*j - C[i]*g' +j*j*( X[i+1]-X[i] )

( j-F[i] <= g' <=j ) (g' 必然小于 j，无需处理)

显然 C[i]*j 和 j*j*( X[i+1]-X[i] ) 为定值，

f[i+1][j]的值由 f[i][ g’ ] - C[i]* g' 决定，

可构造队列q(元素为 g‘ ):

从 0 到 f[i]一一进队（j）

如果 j-q.front()>F[i] 出队

j 进队，保持队列递减

f[i+1][j]=f[i][q[head] ]+ C[i]*( j-q[head] ) - C[i]*g' +j*j*( X[i+1]-X[i] )

复杂度O（N*K）不会 T 了- =（Orz Ak God）

代码如下：

1 #include<cstring> 2 #include<algorithm> 3 #include<cstdio> 4 #include<string> 5 #include<iostream> 6 #include<queue> 7 #define LL long long 8 #define INF 99999999999LL 9 struct Cow{ 10 int x,tot,c; 11 }a[509]; 12 bool cmp(const Cow&X,const Cow&Y){ 13 return X.x<Y.x; 14 } 15 int K,E,n,head,tail; 16 long long f[509][10009]; 17 int q[10009]; 18 int main(){ 19 scanf("%d%d%d",&K,&E,&n); 20 for(int i=1;i<=K;i++) f[1][i]=INF; 21 f[1][0]=0; 22 for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].tot,&a[i].c); 23 std :: sort(a+1,a+n+1,cmp); 24 a[n+1].x=E; 25 for(int i=1;i<=n;i++){ 26 head=1 ; 27 tail=0; 28 LL tot=a[i].tot,c=a[i].c; 29 for(int j=0,k;j<=K;j++){ 30 while(head<=tail&&j - q[head] > tot ) ++head; 31 while(head<=tail&&f[i][j]-j * c<f[i][q[tail]]-q[tail] * c) --tail ; 32 q[++tail]=j; 33 k=j-q[head]; 34 f[i+1][j]=f[i][j-k]+k*c+1LL*j*j*(a[i+1].x-a[i].x); 35 } 36 } 37 printf("%lld",f[n+1][K]); 38 }

View Code

----------------------------------------------------------------

修剪草坪

Description

在去年赢得了小镇的最佳草坪比赛后，约翰变得懒惰了，再也没有修剪过草坪了。现在，新一轮的比赛又开始了，约翰希望能够再次夺冠。然而，约翰的草坪非常脏乱，因此，约翰需要让他的奶牛来完成这项工作。约翰有N头奶牛，平时排成一条直线，编号为1到N。每只奶牛的能力是不同的，第i头奶牛的能力为Ei。靠在一起的奶牛很熟悉，所以如果安排编号连续的K + 1头奶牛在一起工作，她们就会密谋罢工。因此，约翰需要你的帮助。如何挑选奶牛，才能使她们的工作能力之和最高，而且不会罢工呢？

Input Format

第一行：两个用空格隔开的整数：N和K，1 ≤ N ≤ 105，1 ≤ K ≤ N 第二行到N + 1行：第i + 1行有一个整数，表示第i头牛的能力Ei，1 ≤ Ei ≤ 109

Output Format

第一行：单个整数，表示最大的工作能力之和

----------------------------------------------------------------------------

和上题一样想考虑裸Dp
预处理: sum[i] 表示从第一头奶牛到第 i 头奶牛的能力和,
状态: f[i]表示到到第i头可得到的最大能力值和,
转移: f[i]=f[j]+sum[i]-sum[j+1]
比上一题简单,很容易看出sum[i]是个定值,
按 f[j]-sum[j+1] 做单调队列即可,
Ps.注意 k=1 时的情况

代码如下：

1 #include<cstring> 2 #include<algorithm> 3 #include<cstdio> 4 #include<string> 5 #include<iostream> 6 #include<queue> 7 #define INF 99999999 8 #define Max(x,y) if(y>x) x=y 9 #define ll long long 10 using namespace std; 11 ll head,tail,q[100001],p[100001],f[100001],n,k,sum[100001],ans; 12 int main(){ 13 scanf("%lld%lld",&n,&k); 14 for(int i=1;i<=n;i++){ 15 scanf("%d",&sum[i]); 16 sum[i]+=sum[i-1]; 17 q[i]=-INF; 18 } 19 head=1; 20 tail=0; 21 for(ll i=1;i<=k;i++) { 22 f[i]=sum[i]; 23 while(f[i]-sum[i+1]>=q[tail]&&tail>=head) --tail; 24 q[++tail]=f[i]-sum[i+1]; 25 p[tail]=i; 26 ans=max(f[i],ans); 27 } 28 for(ll i=k+1;i<=n;i++){ 29 while(i-p[head]-1>k) ++head; 30 f[i]=max(f[i-2]+sum[i]-sum[i-1],q[head]+sum[i]); 31 while(f[i]-sum[i+1]>=q[tail]&&tail>=head) --tail; 32 q[++tail]=f[i]-sum[i+1]; 33 p[tail]=i; 34 ans=max(f[i],ans); 35 } 36 printf("%lld",ans); 37 }

View Code