题目描述:
给定正整数序列 x1....xn。
- 计算其最长不下降子序列的长度 s。
- 如果每个元素只允许使用一次,计算从给定的序列中最多可取出多少个长度为 s 的不下降子序列。
- 如果允许在取出的序列中多次使用 x1 和 xn(其他元素仍然只允许使用一次),则从给定序列中最多可取出多少个不同的长度为 s 的不下降子序列。
令 a1, a2,…,as 为构造 S 时所使用的下标,b1,b2,…,bs 为构造 T 时所使用的下标。
原题解链接:>here<
思路:第一问我们O(n^2)做出来,把f[i](1<=i<=n)求出来,表示第前i个数的最长递增序列长度。
第二问用最大流,要每个点只使用一次,我们可以把一个点拆为(i,a),(i,b),(i,a)与(i,b)连边,容量为1,然后把所有f[i]为1
的(i,a)点与源点连边,所有f[i]为n的(i,b)点与汇点连边,容量均设置为1,判断如果f[i]=f[j]-1且i的值大于等于j的值,
就把(j,b)对(i,a)连边,容量为1,然后就得到了这个图(偷的hhh)
num = 1 2 3 2 4 f = 1 2 3 3 4
有如下图:
然后跑最大流就是满足条件的序列数量。然后第二问就是把1节点与n节点的流量设置为inf,
注意n的上述操作的前提必须要f[n]==len,而1不需要因为f[1]==1是必然的,也不用再建图,
就原残留网络上再连边,然后再跑一下就可以了。
部分代码:
int n; int f[maxn],len, v[maxn]; int main() { //freopen("test.txt", "r", stdin); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &v[i]); } for (int i = 1; i <= n; i++) { f[i] = 1; for (int j = 1; j <i; j++) { if (v[i] >= v[j]) { f[i] = max(f[i], f[j] + 1); } } len = max(len, f[i]); } if (len == 1) { printf("%d\n",len); printf("%d\n", n); printf("%d\n", n); return 0; } printf("%d\n",len); s = n * 2 + 1, t = s + 1; for (int i = 1; i <= n; i++) { add(i, i + n, 1); if (f[i] == 1) { add(s, i, 1); } if (f[i] == len) { add(i + n, t, 1); } for (int j = 1; j <i; j++) { if (v[i] >= v[j] && f[i] == f[j] + 1) { add(j + n, i, 1); } } } ll ans = dinic(); printf("%lld\n", ans); add(s, 1, inf); add(1, 1 + n, inf); if (f[n] == len)add(n+n, t, inf), add(n, n + n, inf); ans += dinic(); printf("%lld\n",ans); return 0; }