[网络流24题] 最长不下降子序列问题

LOJ 特判 n == 1
注意 最后对 1， n 点得处理就好
HDU 多校 第3场前置知识
I HDU 6611 K Subsequence
所有我先补了这题

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull; 
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
int n; 
int dp[maxn], a[maxn];

int s, t;
int head[maxn], depth[maxn], cur[maxn], cnt;
int nxt[maxn << 2], to[maxn << 2], cap[maxn << 2];  

void ade(int a, int b, int c) {
	to[++cnt] = b, cap[cnt] = c;
	nxt[cnt] = head[a], head[a] = cnt;
}

bool bfs(){
	queue<int> que;
	que.push(s);
	memset(depth, 0, sizeof(depth));
	depth[s] = 1;
	while(!que.empty()) {
		int u = que.front(); que.pop();
		for(int i = head[u]; i != -1; i = nxt[i]) {
			if(cap[i] > 0 && depth[to[i]] == 0) {
				depth[to[i]] = depth[u] + 1;
				que.push(to[i]);
			}
		}
	}
	if(depth[t]) return 1;
	else return 0;
}

int dfs(int u, int dist) {
	if(u == t) return dist;
	for(int &i = cur[u]; i != -1; i = nxt[i]) {
		if(depth[to[i]] == depth[u] + 1 && cap[i] > 0) {
			int tmp = dfs(to[i], min(dist, cap[i]));
			if(tmp > 0) {
				cap[i] -= tmp;
				cap[i ^ 1] += tmp;
				return tmp; 
			}
		}
	}
	return 0;
}

int dinic() {
	int res = 0, d;
	while(bfs()) {
		for(int i = 0; i < n * 2 + 5; i ++) cur[i] = head[i];
		while(d = dfs(s, INF)) res += d;
	}
	return res;
}

int main(){
	cin >> n;
// memset(dd, 0x3f, sizeof dd);
	for(int i = 1; i <= n; i ++) cin >> a[i], dp[i] = 0;
	int ans1 = 0;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j < i; j ++) 
			if(a[j] <= a[i] && dp[j] > dp[i]) dp[i] = dp[j];
		dp[i] ++;
		ans1 = max(ans1, dp[i]);
	}
	cout << ans1 << endl;
	
	memset(head, -1, sizeof head);
	cnt = -1;
	s = 0, t = 2 * n + 1;
	for(int i = 1; i <= n; i ++) {
		if(dp[i] == 1) ade(s, i, 1), ade(i, s, 0);
		if(dp[i] == ans1) ade(i, t, 1), ade(t, i, 0);
		for(int j = 1; j < i; j ++) 
			if(dp[j] + 1 == dp[i] && a[i] >= a[j]) 
				ade(j + n, i, 1), ade(i, j + n, 0);	
	}
	for(int i = 1; i <= n; i ++) ade(i, i + n, 1), ade(i + n, i, 0);
	int ans2 = dinic();
	cout << ans2 << endl;
	
	if(dp[1] == 1) ade(s, 1, INF), ade(1, s, 0);
	ade(1, 1 + n, INF), ade(1 + n, 1, 0);
	
	if(dp[n] == ans1) ade(n + n, t, INF), ade(t, n + n, 0);
	ade(n, n + n, INF), ade(n + n, n, 0); 
	ans2 += dinic(); 
	cout << ans2 << endl; 
	return 0;	
}