【LOJ】#2306. 「NOI2017」蔬菜

题解

从后往前递推

如果我们知道了第i天的最优方案和第i天选择的蔬菜，加入第i天选择的蔬菜数量为S，我们只需要减去最小的S - (i - 1) * M 个蔬菜即可

所以我们只要求出最后一天的蔬菜选择

我们把每个蔬菜拆成c - 1个价值为a和1个价值为a + s，从大到小排序，然后用并查集维护可以选择的位置

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

//#define ivorysi

#define MAXN 100005

#define eps 1e-7

#define mo 974711

#define pb push_back

#define mp make_pair

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

const int P = 100000;

int N,M,K;

int num[MAXN];

int fa[MAXN];

struct node {

    int x,val,c,t;

    friend bool operator < (const node &a,const node &b) {

	return a.val < b.val;

    }

}veg[MAXN * 2];

int MK[MAXN * 10],tot = 0;

int64 ans[MAXN];

bool cmp(node a,node b) {

    return b < a;

}

void Init() {

    scanf("%d%d%d",&N,&M,&K);

    int a,s,c,x;

    for(int i = 1 ; i <= N ; ++i) {

	scanf("%d%d%d%d",&a,&s,&c,&x);

	if(x == 0) {

	    veg[i * 2 - 1] = (node){x,a,c - 1,P};

	    veg[i * 2] = (node){0,a + s,1,P};

	}

	else {

	    int t = (c - 1) / x + 1;

	    veg[i * 2 - 1] = (node){x,a,c - 1 - (t - 1)* x,t};

	    veg[i * 2] = (node){0,a + s,1,t};

	}

    }

    sort(veg + 1,veg + 2 * N + 1,cmp);

}

int find_pos(int x) {

    return fa[x] == x ? x : fa[x] = find_pos(fa[x]);

}

void Solve() {

    for(int i = 1 ; i <= P + 1; ++i) fa[i] = i;

    for(int i = 1 ; i <= 2 * N ; ++i) {

	int s = find_pos(veg[i].t);

	int used = 0;

	while(s && used < veg[i].c + veg[i].x * (veg[i].t - 1)) {

	    int now = veg[i].c + veg[i].x * (veg[i].t - s);

	    now -= used;

	    while(now && num[s] < M) {

		--now;++used;num[s]++;

		MK[++tot] = veg[i].val;

	    }

	    if(num[s] == M) fa[s] = find_pos(s - 1);

	    s = find_pos(s - 1);

	}

    }

    sort(MK + 1,MK + tot + 1);

    for(int i = 1 ; i <= tot ; ++i) ans[P] += MK[i];

    int poi = 1,S = 0;

    for(int i = 1 ; i <= P ; ++i) S += num[i];

    for(int i = P - 1 ; i >= 1 ; --i) {

	ans[i] = ans[i + 1];

	int del = max(S - i * M,0);

	S -= del;

	for(int j = poi ; j <= poi + del - 1; ++j) {

	    ans[i] -= MK[j];

	}

	poi += del;

    }

    int p;

    for(int i = 1 ; i <= K ; ++i) {

	scanf("%d",&p);

	printf("%lld\n",ans[p]);

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    Solve();

}