[雅礼1706 Day 11] delight

天, 第 天在吃饭 (收益 ), 睡觉 (收益 ), 等死之间选其一. 连续 天至少有 天吃饭, 天睡觉. 求最大收益. [bzoj 4842] [Neerc2016]Delight for a Cat 考试的时候只会写暴力状压DP. QAQ

首先, 等死是没有必要的. 因为我们限制的是吃饭,睡觉天数的下界, 而所有权值非负. 不妨假设每天吃饭, 获得 的收益. 选一些日子修改为睡觉, 收益 . 令 .

听了正解感到很迷茫......有两种流派: - 转成线性规划问题, 把式子整一整, 根据流量平衡连边. - 看作一种新的模型, 通过感性认知建模......

后来找到了另一种个人觉得可以接受的流派: - 转化为已知模型, 开开心心地建模.

第一种方法我在考场上尝试过, 然后失败了......主要是因为引入了前缀和作为变量, 但是列出来的式子不能保证每个变量在等号两边至多各出现一次.

经过一番努力, 后来用这种方法做出来了, 但是一点也不优美......一开始建出的图还有负圈 (只会连续最短增广路算法 TAT)......换了一种操作方式, 终于建出了和题解一样的图. 所以问题来了, 我怎么预先知道图有没有负圈......

网络流与线性规划

线性规划问题, 如果每个变量至多在等号两边各出现一次, 就可以用费用流跑.

每个等式一个点.

如果变量 在 号等式的右边, 号等式的左边出现, 就连一条从 到 的边. 如果只在 号等式的左边出现, 连 到 . 如果只在 号等式的右边出现, 连 到 .

常量同理. 要让代表常量的边流满, 所以跑最小/大费用最大流.

本题建出来的图是这样的: - 除源, 汇外, 共有 个点. - 向前 个点连边, 向 连边 , 流量为 , 费用为 . 如果目标点不存在, 则连向 . (I) - 向 , 向 , 向 连边, 流量为 , 费用为 . (II) - 限制总流量不超过 .

是不是很像区间k覆盖问题呢?

区间k覆盖 有 个区间 , 收益为 . 选出一些区间, 使数轴上所有点被覆盖不超过 次. 求最大收益.

- 设 (离散化后) 涉及到的值域为 , 令 . - 向 连边, 流量为 , 费用为 . - 向 连边, 流量为 或 , 费用为 . - 限制总流量不超过 .

每个流量对应一组互不相交的区间, 因此每个点不会被覆盖多于 次.

每个合法方案可以被分解成不超过 组互不相交的区间. 假设努力地去掉 组互不相交的区间后, 剩下了一个区间 . 这意味着每一组都存在相邻的两个区间 使得 . 这是不可能的.

注意, 这里是半开半闭区间. 这样才能保证 只覆盖点 一次.

最大费用可以在满流的时候取到, 所以可以跑最大费用最大流.

本题就是区间k覆盖问题. 我们用右端点 代表区间 , 则选择点 使 的计数器++. 每个计数器的值必须在 的范围.

更准确地说: 我们有 个区间, 第 个为 , 权值等于 , 每个点被覆盖的次数在 中, 最大化权值和.

令 .

新颖之处在于, 本问题中, 每个点被覆盖的次数有下界.

这个网络的最大流为 . 对 画一条纵截线, 流量最大时, 穿出这条线的净流即为 . 点 被覆盖的次数等于纵截线割开的 (I) 类边的流量之和. 那么, 限制 (II) 类边 的容量为 , (I) 类边的流量之和便不会小于 .

typedef long long ll;

const int N = 1001;
const ll inf = 1LL<<60;

struct MinCostFlow
{
	const static int V = N + 3;
	bool inq[V];
	int s, t, n, p[V], adj[V];
	ll d[V];
	queue<int> Q;
	
	struct Edge
	{
		int to, c, w, next;
	} E[4*N + 2];

	void add(int u, int v, int c, int w)
	{
		static int ptr = 2;
		E[ptr] = (Edge){v, c, w, adj[u]};
		adj[u] = ptr++;
		E[ptr] = (Edge){u, 0, -w, adj[v]};
		adj[v] = ptr++;
	}

	bool spfa(ll& init, ll& flow, ll& cost)
	{
		fill_n(d, n, -inf);
		Q.push(s);
		d[s] = 0;
		while (!Q.empty())
		{
			int u = Q.front(); Q.pop();
			inq[u] = false;
			for (int i = adj[u]; i; i = E[i].next)
			{
				int v = E[i].to;
				if (E[i].c && d[v] < d[u] + E[i].w)
				{
					p[v] = i;
					d[v] = d[u] + E[i].w;
					if (!inq[v])
						inq[v] = true, Q.push(v);
				}
			}
		}
		if (d[t] == -inf) return false;
		ll f = init;
		for (int v = t; v != s; v = E[p[v]^1].to)
			f = min(f, (ll)E[p[v]].c);
		for (int v = t; v != s; v = E[p[v]^1].to)
			E[p[v]].c -= f, E[p[v]^1].c += f;
		init -= f;
		flow += f;
		cost += d[t] * f;
		return true;
	}

	ll main(int _s, int _t, int _n, ll _i)
	{
		s = _s, t = _t, n = _n;
		ll c = 0, f = 0, i = _i;
		while (i && spfa(i, f, c)) ;
		return c;
	}
} F;

int s[N], e[N];

int main()
{
	int n, k, S, E;
	ll sum = 0;
	scanf("%d%d%d%d", &n, &k, &S, &E);
	rep (i, 1, n+1) scanf("%d", s+i), sum += s[i];
	rep (i, 1, n+1) scanf("%d", e+i);
	rep (i, 1, k+1) F.add(0, min(i, n-k+1), 1, e[i]-s[i]);
	rep (i, k+1, n+1) F.add(i-k, min(i, n-k+1), 1, e[i]-s[i]);
	rep (i, 0, n-k+1) F.add(i, i+1, k-S-E, 0);
	printf("%lld\n", sum + F.main(0, n-k+1, n-k+2, k-S));
	return 0;
}