夏晓光(loveJY)的博客

NOI2017D2T2

说实话,D2T2就这种程度吗?甚至不能称为黑题吧233

开题不难发现我们再每天要准确做出一个决策才行,要不然这个数据范围根本动态规划不了的

按照某种规律直接决策不就是贪心吗?

而且这个也很像之前做的CF集训队作业题那个题就是每天竹子会上涨,可以通过时光倒流变成竹子要下跌,为题就完全变样子了

所以这个题也可以用时光倒流的做法,变成倒着运菜进来,那么显然我们每次选择最优的就行了,难度在于模拟啊

这里提供一种不一样的做法:我们把时光倒流的本质思考出来,单独分析每个菜

1. 每个菜都是在他最贵的时候被选择卖,也就是对应每次选最优的
2. 每个菜都是在他快要腐烂的时候被卖,也就是对应倒着运菜

有了这两个性质,我们只需要得到一个卖菜序列,然后在卖菜序列上通过并查集操作就行了

具体看code:

#include<bits/stdc++.h>
using namespace std;
#define mkp(x,y) (make_pair(x,y))
#define ll long long
const int MAXN=1e6+7,mx=1e5+7;
int n,m,k;
int a[MAXN],s[MAXN],c[MAXN],x[MAXN];
int fa[MAXN],num[MAXN];
ll ans[MAXN];
priority_queue<pair<int,int> > q;
inline int getf(int x) {
	return x==fa[x]?x:fa[x]=getf(fa[x]);
}

int main() {
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1; i<=n; ++i) {
		scanf("%d%d%d%d",&a[i],&s[i],&c[i],&x[i]);
		q.push(mkp(a[i]+s[i],i));
	}
	for(int i=1; i<=mx; ++i)fa[i]=i,num[i]=m;
	int cnt=0,profit,t,day;
	while(!q.empty()) {
		profit= q.top().first,t=q.top().second;
		q.pop();
		if(!x[t])day=getf(mx);
		else day=getf(min(mx,(c[t]-1)/x[t]+1));
        //找到要T的时间
		if(!day)continue;
		c[t]--;
		num[day]--;
		cnt++;
        //处理每天能卖的上限
		if(!num[day])fa[day]=getf(day-1);
		if(c[t])q.push(mkp(a[t],t));
		ans[cnt]=ans[cnt-1]+profit;
        //卖菜序列
	}
	int qaq;
	while(k--)scanf("%d",&qaq),printf("%lld\n",ans[min(cnt,m*qaq)]);
	return 0;
}