「NOI2017」蔬菜

你的仓库里有 $n$ 种蔬菜,每天最多销售 $m$ 个单位的蔬菜

第 $i$ 种蔬菜有 $c_i$ 单位的库存,每天固定会有 $x_i$ 个单位变质从而不能再用于销售

这种蔬菜的单位收益为 $a_i$ ,同时,对其进行的第一次销售（卖出去的第一个单位）会产生 $s_i$ 的额外收益。

你想知道销售 $p$ 天的最大收益。多组询问。

$n\le 10^5, m\le 10, p\le 10^5, a, c, x, s \le 10^9$

Link

LOJ2306

Solution

好恶心的一道题

如果我们知道了第$t$天最优策略卖出的蔬菜集合$S$，那么$t-1$天卖出的蔬菜就是把$S$中权值最小的$m$个元素去掉形成的集合

那么只需要考虑最后一天的集合，然后倒退即可

求最后一天的集合时有一些性质：

• 贪心考虑，从权值大到小考虑
• 倒着考虑，把腐烂看成新增，每个蔬菜尽量往后放，从腐烂的那天往前放
• 每种蔬菜第一次卖出的那一单位可以看成一个新的蔬菜，并且可以视为最后腐烂的
• 每次暴力找哪一天还有剩余，用并查集优化这个过程

这题还有不少细节，就不一一列举了，不如直接看代码

---

UPD 19.8.16

放一下网络流做法：

总共四类点，从左往右一次为：$S$，天，蔬菜，$T$

连这些边：

1. $S$向每一天连边$(m,0)$, 以限制每种蔬菜可以卖多少个.

2. 第$i$天向第$(i+1)$连边$(inf,0)$, 这意味着如果后面的天没有把它们的蔬菜卖完, 前面的天就可以到后面去继续后面的蔬菜.

3. 把每种蔬菜拆成$\frac{c-1}{x}+1$份，前$\frac{c-1}{x}$份每份$x$，最后一份是

   每天向这一天会腐烂的那份蔬菜连边$(inf, 0)$

4. 每份蔬菜向$T$连边，容量为这份的数量，费用为$a$

5. 每种蔬菜的最后一份向$T$多连一条$(1, a+s)$的边

因为只有蔬菜向$T$有费用，所以不会退流

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;

int N, M, K, Max = 1e5;
struct item
{
	int p, v, t, x;
};
vector <item> A;
priority_queue <pii, vector <pii>, greater <pii> > Q;
LL Ans[Maxn];

namespace DSU
{
	int fa[Maxn];
	inline void init (int n = 1e5) { for (int i = 1; i <= n; ++i) fa[i] = i; }
	inline int get_fa (int x) { return fa[x] == x ? x : fa[x] = get_fa (fa[x]); }
}

int Rest[Maxn];

inline int cmp (item a, item b) { return a.p > b.p; }

inline void Init ()
{
	DSU :: init ();
	for (int i = 1; i <= Max; ++i) Rest[i] = M;
	sort (A.begin(), A.end(), cmp);

	for (int i = 0; i < A.size(); ++i)
	{
		int p = A[i].p, v = A[i].v, t = A[i].t, x = A[i].x;
		int res = 0, sum = 0;
		while (1)
		{
			int to = DSU :: get_fa (t);
			if (!to) break;
			res = min (v, res + (t - to + 1) * x);
			int now = min (Rest[to], res);
			res -= now, Rest[to] -= now, v -= now, sum += now;
			if (!v) break;
			if (!Rest[to]) DSU :: fa[to] = DSU :: fa[to - 1];
			t = to - 1;
			if (!t) break;
		}
		Ans[Max] += (LL) p * sum;
		if (sum) Q.push (mp (p, sum));
	}
}

inline void Solve ()
{
	Init();

	int sum = 0;
	for (int i = 1; i <= Max; ++i) sum += M - Rest[i], Rest[i] = 0;
	for (int i = 1; i <= Max; ++i) Rest[i] = min (sum, M), sum = max (0, sum - M);

	for (int i = Max - 1; i >= 1; --i)
	{
		Ans[i] = Ans[i + 1];

		while (!Q.empty() && Rest[i + 1])
		{
			pii now = Q.top(); Q.pop();
			int use = min (Rest[i + 1], now.y);
			Ans[i] -= (LL) now.x * use;
			if (use == Rest[i + 1])
			{
				Q.push (mp (now.x, now.y - Rest[i + 1]));
				break;
			}
			Rest[i + 1] -= now.y;
		}
	}

	for (int i = 1; i <= K; ++i) printf("%lld\n", Ans[read<int>()]);
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), K = read<int>();
	for (int i = 1; i <= N; ++i)
	{
		int p = read<int>(), a = read<int>(), v = read<int>(), x = read<int>();
		if (x)
		{
			int t = (v - 1 + x) / x;
			A.pb ((item){p, (t - 1) * x, t - 1, min (M, x)});
			A.pb ((item){p + a, 1, t, 1});
			A.pb ((item){p, (v - 1) % x, t, (v - 1) % x});
		}
		else
		{
			A.pb ((item){p, v - 1, Max, M});
			A.pb ((item){p + a, 1, Max, 1});
		}
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}