Codeforces Gym 101194C Mr. Panda and Strips（2016 EC-Final，区间DP预处理 + 枚举剪枝）

题目链接 2016 EC-Final

题意现在要找到数列中连续两个子序列（没有公共部分）。要求这两个子序列本身内部没有重复出现的数。

　　求这两个子序列的长度的和的最大值。

首先预处理一下。令$f[i][j]$为$i$到$j$这段数字里面能找到的符合题意条件的区间的长度的最大值。

这段预处理时间复杂度$O(n^{2})$

然后$O(n^{2})$枚举第一个区间，如果出现重复的数字了那么的第二层循环break掉。

记当前枚举到的区间的长度为$s$

在刚刚枚举的基础上，考虑枚举到的这个区间的右边的这些数，如果某个数字在前面那个区间中出现过了，

那么这个位置标记$1$，否则标记$0$。

做一次$O(n)$的扫描，每次找到连续的最多的$0$的区间，记为$c_{x}...c_{y}$

用$s + f[x][y]$更新答案

若当前枚举能得到的最优答案小于已经得到的答案了，那么就直接输出。

时间复杂度$O(n^{3})$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 1e3 + 3;

int f[N][N], a[N], b[N];

int T, n, cnt, ans, ca = 0;

bitset <N> tmp, bit;

vector <int> v[N];

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d", &n);

		rep(i, 1, n) scanf("%d", a + i), b[i] = a[i];

		sort(b + 1, b + n + 1);

		cnt = unique(b + 1, b + n + 1) - b - 1;

		rep(i, 1, n) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;

		rep(i, 1, n) v[i].clear();

		rep(i, 1, n) v[a[i]].push_back(i);

		rep(i, 0, n + 1) rep(j, 0, n + 1) f[i][j] = 0;

		rep(i, 1, n){

			tmp.reset();

			rep(j, i, n){

				if (tmp[a[j]]) break;

				tmp.set(a[j]);

				f[i][j] = j - i + 1;

			}

		}

		ans = 0;

		dec(i, n - 1, 1) rep(j, i + 1, n) f[i][j] = max(f[i][j], max(f[i + 1][j], f[i][j - 1]));

		rep(i, 1, n){

			if (n - i + 1 <= ans) break;

			tmp.reset();

			bit.reset();

			rep(j, i, n){

				if (tmp[a[j]]) break;

				tmp.set(a[j]);

				for (auto u : v[a[j]]) bit.set(u);

				int now = 0;

				int l = j + 1;

				rep(r, j + 1, n) if (!bit[r]) now = max(now, f[l][r]); else l = r + 1;

				if (j - i + 1 + now > ans){

					ans = j - i + 1 + now;

				}

			}

		}

		printf("Case #%d: %d\n", ++ca, ans);

	}

	return 0;

}

巴特西

Codeforces Gym 101194C Mr. Panda and Strips（2016 EC-Final，区间DP预处理 + 枚举剪枝）

最新文章

热门文章