题意

有n种物品，每种物品有费用，价值和数量三个值。 有m个询问x y，求有x元且不选第y种物品的情况下最多可以获得多少价值。 n,y<=1000,m<=300000

分析

我打的水法：求一次前缀背包和后缀背包，对于每个询问分别枚举前缀价格和后缀价格即可。 复杂度O(nq)

正解：分治，设solve(i,j)表示不选i到j种物品时能获得的最大价值。显然solve(l,r)可以更新到solve(l,mid)和solve(mid+1,r) 对solve(i,i)统计答案即可。

然而笔者懒癌晚期，不想打了。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 1005 using namespace std; int n,m,q[N],f[N][N],g[N][N]; struct object{int a,b,c;}o[N]; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void dp1() { for (int i=1;i<=n;i++) { for (int j=0;j<o[i].a;j++) { int head=1,tail=0; for (int k=j;k<=1000;k+=o[i].a) { f[i][k]=f[i-1][k]; while (head<=tail&&(k-q[head])/o[i].a>o[i].c) head++; if (head<=tail) f[i][k]=max(f[i][k],f[i-1][q[head]]+o[i].b*(k-q[head])/o[i].a); while (head<=tail&&f[i-1][q[tail]]+o[i].b*(k-q[tail])/o[i].a<=f[i-1][k]) tail--; q[++tail]=k; } } } } void dp2() { for (int i=n;i>=1;i--) { for (int j=0;j<o[i].a;j++) { int head=1,tail=0; for (int k=j;k<=1000;k+=o[i].a) { g[i][k]=g[i+1][k]; while (head<=tail&&(k-q[head])/o[i].a>o[i].c) head++; if (head<=tail) g[i][k]=max(g[i][k],g[i+1][q[head]]+o[i].b*(k-q[head])/o[i].a); while (head<=tail&&g[i+1][q[tail]]+o[i].b*(k-q[tail])/o[i].a<=g[i+1][k]) tail--; q[++tail]=k; } } } } int main() { n=read(); for (int i=1;i<=n;i++) { o[i].a=read();o[i].b=read();o[i].c=read(); } dp1();dp2(); m=read(); for (int i=1;i<=m;i++) { int x=read()+1,y=read(),ans=0; for (int k=0;k<=y;k++) ans=max(ans,f[x-1][k]+g[x+1][y-k]); printf("%d\n",ans); } return 0; }