[bzoj 4873] [Shoi2017]寿司餐厅

n种寿司, 第i种寿司有代号a[i], 区间[i,j]有美味度d[i][j] (i≤j). 每种寿司的份数无限, 取的次数无限. - 每次取走的寿司必须是连续的一段, 且每种各取一份. - 取[l,r]内的寿司会获得[l,r]所有子区间 (包括[l,r]) 的美味度之和. 总美味度是每次获得的美味度之和的累加, 但是每个d[i][j]只会被加一次. - 如果一共吃过c (c>0) 种代号为a的寿司, 需要支付(ma^2+ca)元钱, m是对于所有代号的寿司均相等的常数.

求总美味度减去花费的总钱数的最大值. (n≤100, a[i]≤1000, d[i][j]是整数, 可能不是正的) 看起来很像网络流, 但是, 每个d[i][j]只会被加一次, 吃过代号为a的寿司则支付ma^2 (不论吃了多少), 这两个怎么处理呢?

出题人爱吃寿司的Kiana在APIO讲课时说, 这是最大权闭合子图.

咦? 确实很符合最大权闭合子图的模型......

区间[l,r] (l<r) 向[l,r-1]和[l+1,r]连边, [l,l]向表示代号的点连边即可. .

积累了一个经验: a或b发生将导致c, 但是它们同时发生并不会使c的影响扩大, 可以考虑一下最大权闭合子图. 有种数字电路的感觉~

const int N = 100, inf = 1e9;

struct MaximumFlow {
	const static int e_size = 30500, v_size = 5160;
	
	struct Edge {
		int to, c, nxt;
	} E[e_size];

	int ptr, n, s, t, lv[v_size], cur[v_size], adj[v_size];

	MaximumFlow(): ptr(2) {}

	inline void add(int u, int v, int f)
	{
		E[ptr] = (Edge){v, f, adj[u]};
		adj[u] = ptr++;
		E[ptr] = (Edge){u, 0, adj[v]};
		adj[v] = ptr++;
	}

	bool bfs()
	{
		queue<int> Q;
		fill_n(lv, n, -1);
		lv[s] = 0;
		Q.push(s);

		while (!Q.empty()) {
			int u = Q.front(); Q.pop();
			for (int i = adj[u]; i; i = E[i].nxt) {
				int v = E[i].to;
				if (E[i].c && lv[v] == -1) {
					lv[v] = lv[u] + 1;
					Q.push(v);
				}
			}
		}

		return lv[t] != -1;
	}

	int dfs(int u, int f)
	{
		if (u == t) return f;
		int res = f;
		for (int& i = cur[u]; i; i = E[i].nxt) {
			int v = E[i].to;
			if (E[i].c && lv[v] == lv[u] + 1) {
				int d = dfs(v, min(E[i].c, res));
				res -= d;
				E[i].c -= d;
				E[i^1].c += d;
				if (!res) break;
			}
		}
		return f-res;
	}
	
	int solve(int _n, int _s, int _t)
	{
		n = _n, s = _s, t = _t;
		int f = 0;
		while (bfs()) {
			rep (i, 0, n) cur[i] = adj[i];
			f += dfs(s, inf);
		}
		return f;
	}
} solver;

int s, t, top, sum, H[N], a[N], id[N][N];

inline void link(int v, int w)
{
	if (w > 0) {
		sum += w;
		solver.add(s, v, w);
	} else {
		solver.add(v, t, -w);
	}
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	rep (i, 0, n) {
		scanf("%d", a+i);
		H[top++] = a[i];
	}
	sort(H, H+top);
	top = unique(H, H+top) - H;
	s = n*(n+1)/2 + top, t = s+1;

	rep (i, 0, top) link(i, -m*H[i]*H[i]);
	
	int cnt = top, d;

	rep (i, 0, n) {
		scanf("%d", &d);
		link(id[i][i] = cnt++, d - a[i]);
		rep (j, i+1, n) {
			scanf("%d", &d);
			link(id[i][j] = cnt++, d);
		}
	}

	rep (i, 0, n) {
		solver.add(id[i][i], lower_bound(H, H+top, a[i]) - H, inf);
		rep (j, i+1, n) {
			solver.add(id[i][j], id[i][j-1], inf);
			solver.add(id[i][j], id[i+1][j], inf);
		}
	}
	
	printf("%d\n", sum - solver.solve(cnt+2, s, t));
	return 0;
}