zoj3161 Damn Couples

不想打题面了，题面戳这里

这道题目的模型转换地有点猛。首先我们肯定需要让老板把那些不相邻的人的卡牌放在前面，这样他们就作废了。然后剩下的卡牌就都是相邻人之间的了。我们就可以把这个序列分成若干个联通块，每个联通块内相邻的人之间有连边。此时显然不同联通块是互不干扰的，我们只需要知道每个联通块内剩下的人最多可以是多少就可以了。这个我们就可以dp了。

\(f_i\)表示大小为\(i\)的联通块内最多能剩多少人，那么方程就和显然了。

\[f_i = \max \{ f_j+f_{i-j-1} \},j < i
\]

最后对统计所有联通块答案求和即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

const int maxn = 510;

int N,M,f[maxn],father[maxn],ans;

inline int find(int x) { return father[x] != x?father[x] = find(father[x]):x; }

int main()

{

	freopen("3161.in","r",stdin);

	freopen("3161.out","w",stdout);

	f[1] = 1; f[0] = 0;

	for (int i = 2;i <= 500;++i) for (int j = 1;j < i;++j) f[i] = max(min(f[j-1]+f[i-j],f[j]+f[i-j-1]),f[i]);

	while (scanf("%d %d",&N,&M) != EOF)

	{

		ans = 0;

		for (int i = 0;i < N;++i) father[i] = i;

		for (int i = 1,a,b;i <= M;++i)

		{

			scanf("%d %d",&a,&b);

			if (a > b) swap(a,b);

			if (b - a == 1)

			{

				int r1 = find(a),r2 = find(b);

				father[r2] = r1;

			}

		}

		for (int i = 0,j;i < N;++i)

		{

			for (j = i;j < N&&find(j) == i;++j);

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

		}

		printf("%d\n",ans);

	}

	fclose(stdin); fclose(stdout);

	return 0;

}