[HNOI2005]星际贸易

DP 单调队列

题面

要素太多，还是自己看吧

解析

如果要求贸易额最大，就相当于：
有$n$个物品（星球），每个物品价值为$v_i$（每个星球能卖$v_i$），现装入一个体积为$m$（载重量为$m$）的背包，最大化装入物品体积之和。
一个裸背包$DP$即可解决第一问。

并且我们可以顺手得出，达到该贸易额，必须要停靠哪些站。
（当然，为了维护和加油，应该还需要停靠另外一些站）

接下来要求利润最大，就是要求加油与维修的费用最少。
由于$n\leq2000$，所以状态只能设两维：
$f[i][j]$表示到第$i$个星球时油量为$j$的最小花费。

相关转移：
加油：直接$f[i][j-1]->f[i][j]$即可。
维护：从前面停靠了的站转移过来（枚到最近那个必须停靠的星球就行）。
这样好像是$O(n^3)$的。。。

然后膜了一发$yyb$，发现维护的转移过程可以用单调队列优化（先尾后进后首）。
很有道理啊。
于是就做完了。
复杂度$O(n^2)$。

细节问题：$m,R$混用、背包转移不全、单调队列入出队条件设错（应该以当前$DP$值为参照，而不是队列内）。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=2500;
int n,m,V,len,A[N],B[N],L[N],P[N],F[N],dp[N][N<<1],pos,ans1,ans2,Q[N<<1][N],h[N<<1],t[N<<1];
bool vis[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int max(re int x,re int y){return x>y?x:y;}
il int min(re int x,re int y){return x<y?x:y;}
int main()
{
  n=gi();m=gi();V=min(gi(),2*n);len=gi();
  fp(i,1,n)
    {
      A[i]=gi();B[i]=gi();L[i]=gi();P[i]=gi();F[i]=gi();
      if(L[i]-L[i-1]>len) return puts("Poor Coke!"),0;
    }
  memset(dp,-63,sizeof(dp));dp[0][0]=0;
  fp(i,1,n)
    fp(j,0,m)
    {
      if(j>=A[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-A[i]]+B[i]);
      dp[i][j]=max(dp[i][j],dp[i-1][j]);
    }
  fp(i,1,m) if(dp[n][pos]<dp[n][i]) pos=i;
  ans1=dp[n][pos];
  fq(i,n,1) if(dp[i][pos]!=dp[i-1][pos]) vis[i]=1,pos-=A[i];
  memset(dp,63,sizeof(dp));dp[0][V]=0;Q[V][t[V]++]=0;
  fp(i,1,n)
    fp(j,0,V)
    {
      if(P[i]&&j) dp[i][j]=min(dp[i][j],dp[i][j-1]+P[i]);
      if(h[j+2]<t[j+2]) dp[i][j]=min(dp[i][j],dp[Q[j+2][h[j+2]]][j+2]+F[i]);
      if(vis[i]) h[j]=t[j]=0;//can't avoid
      while(h[j]<t[j]&&dp[Q[j][t[j]-1]][j]>=dp[i][j]) --t[j];
      Q[j][t[j]++]=i;
      while(h[j]<t[j]&&L[i+1]-L[Q[j][h[j]]]>len) ++h[j];
    }
  pos=0;
  fp(i,1,V) if(dp[n][i]<dp[n][pos]) pos=i;
  ans2=dp[n][pos];
  if(ans2>1e9) return puts("Poor Coke!"),0;
  printf("%d %d\n",ans1,ans1-ans2);
  return 0;
}