[NOI2017]蔬菜

题目描述

大意就是有\(n\)种物品,第\(i\)个物品有\(c_i\)个,单价是\(a_i\)。然后每天你可以卖出最多\(m\)个物品。每天结束后第\(i\)种物品会减少\(x_i\)个。第一次出售\(i\)物品时还会额外获得\(s_i\)的收益。

每次询问给出\(p\),问\(p\)天能得到的最大收益。

\(1\leq n,p\leq 10^5,1\leq m\leq 10,1\leq a_i,c_i\leq 10^9\)。

神仙题啊!不会网络流,不会贪心,直接自闭。

Orz

60分的网络流做法

因为很容易发现这个题状态太大,无法\(DP\),所以我们考虑费用流之类的东西。然后我们发现这个题每个物品的上限时刻在变化,很难建图。

对于这种流量变化的费用流我们考虑拆点。我们将每种蔬菜拆成\(P\)个点,第\(i\)个点到汇点的流量就是第\(i\)天比第\(i+1\)天多的数量。我们还应该额外拆一个点表示第一次出售。然后第\(i\)个点向第\(i+1\)个点连边。

我们增广\(P\)次,就得到了\(1\)到\(P\)的答案。

100分的贪心算法

我们发现每天有蔬菜减少非常不好做,于是我们考虑倒着做。这样相当于每天我们会得到一些蔬菜。所以我们就可以每次选收益最大的蔬菜来卖。

具体实现有点复杂。先开一个堆。记录每种蔬菜最晚在什么时候出现。当倒推到第\(i\)天时,将在最晚在当天出现的蔬菜丢进堆里。每次取堆顶的蔬菜来卖。

这样我们就得到了\(P\)天的答案。

然后考虑递推出\(1\)到\(P-1\)的答案。相当于说我们要把卖出的蔬菜删除掉。一个比较显然的结论就是我们尽量在天数偏小的时候删除(因为我们卖蔬菜肯定也是越早卖越好)。删除的时候就一直删除当前价值最小的。

不用考虑会不会删除操作时出现了不合法的情况。因为我们发现删除的时间是没有影响的。可以这么感性理解分析:假设我们递推到第\(i\)天,要删除一些第\(k\)种蔬菜,那么我们就将相应的卖出操作撤销,在它之后的卖出操作全部提前,这肯定也是合法的。

据说这就是模拟费用流。

代码:

#include<bits/stdc++.h>
#define ll long long
#define N 100005 using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;} int n,m,k;
ll ans;
int a[N],s[N],c[N],x[N];
struct node {
ll id,val;
node() {val=id=0;}
node(int i,int v) {val=v,id=i;}
bool operator <(const node &a)const {return val<a.val;}
};
priority_queue<node>q;
const int P=100000;
int sold;
vector<int>ap[N];
vector<int>tem;
int used[N];
ll Ans[N];
int main() {
n=Get(),m=Get(),k=Get();
for(int i=1;i<=n;i++) {
a[i]=Get(),s[i]=Get(),c[i]=Get(),x[i]=Get();
if(!x[i]) ap[P].push_back(i);
else ap[min(P,(c[i]+x[i]-1)/x[i])].push_back(i);
} for(int i=P;i>=1;i--) {
for(int j=0;j<ap[i].size();j++) {
q.push(node(ap[i][j],s[ap[i][j]]+a[ap[i][j]]));
}
tem.clear();
int res=m;
while(res) {
if(!q.size()) break;
int id=q.top().id,val=q.top().val;
q.pop();
if(!used[id]) {
res--;
used[id]=1;
ans+=val;
q.push(node(id,a[id]));
} else {
int now=min(res,c[id]-used[id]-(i-1)*x[id]);
res-=now;
used[id]+=now;
ans+=1ll*now*val;
if(used[id]<c[id]) tem.push_back(id);
}
}
sold+=m-res;
for(int j=0;j<tem.size();j++) q.push(node(tem[j],a[tem[j]]));
} while(q.size()) q.pop();
for(int i=1;i<=n;i++) {
if(used[i]==1) q.push(node(i,-s[i]-a[i]));
else if(used[i]>1) q.push(node(i,-a[i]));
} Ans[P]=ans;
for(int i=P;i>1;i--) {
tem.clear();
int res=max(0,sold-(i-1)*m);
while(res) {
if(!q.size()) break;
int id=q.top().id,val=q.top().val;
q.pop();
if(used[id]==1) {
sold--;
used[id]--;
res--;
ans+=val;
} else {
int now=min(res,used[id]-1);
used[id]-=now;
res-=now;
ans+=1ll*now*val;
sold-=now;
if(used[id]==1) q.push(node(id,-s[id]-a[id]));
else q.push(node(id,-a[id]));
}
}
Ans[i-1]=ans;
}
while(k--) {
int x=Get();
cout<<Ans[x]<<"\n";
}
return 0;
}
05-11 14:04