【USACO】又买饲料单调队列dp

题目描述

约翰开车回家，又准备顺路买点饲料了（咦？为啥要说“又”字？）回家的路程一共有 E 公里，

这一路上会经过 N 家商店，第 i 家店里有 F i 吨饲料，售价为每吨 C i 元。约翰打算买 K 吨饲料，他

知道商家的库存是足够的，至少所有店的库存总和不会少于 K。除了购买饲料要钱，运送饲料也是

要花油钱的，约翰的卡车上如果装着 X 吨饲料，那么他行驶一公里会花掉 X² 元，行驶 D 公里需要

DX² 元。已知第 i 家店距约翰所在的起点有 X i 公里，那么约翰在哪些商店买饲料运回家，才能做到

最省钱呢？

输入

• 第一行：三个整数 K，E 和 N，1 ≤ K ≤ 10000,1 ≤ E ≤ 500,1 ≤ N ≤ 500

• 第二行到第 N + 1 行：第 i + 1 行有三个整数 X i ，F i 和 C i ，0 < X i < E,1 ≤ F i ≤ 10000,1 ≤

C i ≤ 10 ⁷

输出

• 单个整数：表示购买及运送饲料的最小费用

样例输入

2 5 3 3 1 2 4 1 2 1 1 1

样例输出

提示

在离家较近的两家商店里各购买一吨饲料，

则花在路上的钱是 1 + 4 = 5，花在店里的钱是

2 + 2 = 4

题解：

这题需要一种奇怪的思想：我们知道一顿饲料如果买了，必将一直影响到最后，于是我们将后来的消费就算到状态里去

于是可以定义f[i][j]表示前i个买j吨一直到终点的花费.然后发现可以消维.

保留f[j]即可

定义d[i]为i到终点的距离.

f[j]=min(f[k]+j^2*d[i]-k^2*d[i]+j*F[i])

把k有关的全部都移项移出来,就可以放到单调队列里

单调队列动规：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=505,M=10005;
typedef long long ll;
struct node
{
  ll x,w,v;
}a[N];
ll f[M],q[M],id[M];
bool comp(const node &p,const node &q){return p.x<q.x;}
int main()
{
  int n,m,e;
  scanf("%d%d%d",&m,&e,&n);
  for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].w,&a[i].v);
  sort(a+1,a+n+1,comp);
  for(int i=1;i<=n;i++)a[i].x=e-a[i].x;
  for(int i=1;i<=m;i++)f[i]=2e16;
  f[0]=0;
  ll tmp;int l,r;
  for(int i=1;i<=n;i++)
   {   
      l=r=1;q[l]=0;id[l]=0;
      for(int j=1;j<=m;j++)
    {
      while(l<r && j-id[l]>a[i].w)l++;
      tmp=f[j];
      f[j]=min(f[j],q[l]+j*j*a[i].x+j*a[i].v);
      while(l<=r && tmp-j*j*a[i].x-j*a[i].v<=q[r])r--;
      q[++r]=tmp-j*j*a[i].x-j*a[i].v;id[r]=j;
    }
    }
  printf("%lld
",f[m]);
  return 0;
}

70分暴力动规：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N=505,M=10005;
 8 const ll xy=2e15;
 9 struct node
10 {
11   int w,v,x;
12 }a[N];
13 ll F[N][M];
14 bool comp(const node &p,const node &q){return p.x<q.x;}
15 int main()
16 {
17   freopen("pp.in","r",stdin);
18   int n,m,e;
19   scanf("%d%d%d",&m,&e,&n);
20   for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].w,&a[i].v);
21   a[++n].x=e;
22   sort(a+1,a+n+1,comp);
23   for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)F[i][j]=xy;
24   F[0][0]=0;
25   ll now;int tmp;
26   for(int i=1;i<=n;i++)
27     {
28       for(int j=0;j<=m;j++)
29     {
30       tmp=j-a[i].w>=0?j-a[i].w:0;
31       if(F[i-1][tmp]==xy)break;
32       for(int k=tmp;k<=j;k++)
33         {
34           now=F[i-1][k]+k*k*(a[i].x-a[i-1].x)+a[i].v*(j-k);
35           if(now<F[i][j])F[i][j]=now;
36         }
37         }
38     }
39   printf("%lld
",F[n][m]);
40 }