[JZOJ 5600] Arg

题意：求最少LIS覆盖...

思路：

计算\(LIS\)时我们一般用\(dp\)表示到当先位置时以当前位置结尾的\(LIS\)最长长度。

那么这个数组保证单调不降，我们考虑二进制表示。

然后就是转移了...

不过蜜汁\(RE\)啊，自测能过...

#include <bits/stdc++.h>

using namespace std;

inline int read(){

	int q=0,f=1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;ch=getchar();

	}

	while(isdigit(ch)){

		q = q * 10 + ch - '0';

		ch = getchar();

	}

	return q*f;

}

int n;

int ans;

int f[20010000];

int c[20];int m;

int wtf[20];

int a[20];

int c2[20];

inline void dfs(int x,int lim,int k) {

	if(x > n) {

		if(!lim) ans += f[k];

		return;

	}

	k += c[x - 1];

	dfs(x + 1,lim,k);

	k += c[x - 1];

	dfs(x + 1,lim - 1,k);

}

int main () {

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

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

	scanf("%d %d",&n,&m);

	for(int i = 1;i <= m; ++i) {

		scanf("%d",&a[i]);

	}

	c[0] = c2[0] = 1;

	for(int i = 1;i <= n; ++i) {

		c[i] = c[i - 1] * 3;

		c2[i] = c2[i - 1] * 2;

	}

	f[0] = 1;

	for(int i = 0;i <= c2[n] - 2; ++i) {

		bool ok = 1;

		bool tag = 1;

		for(int j = 1;j <= m; ++j) {

			if((i & c2[a[j] - 1]) == 0) {

				ok = 0;

			}

			else if(!ok) {

				tag = 0;

				break;

			}

		}

		if(tag) {

			for(int ii = i;1;ii = (ii - 1) & i) {

				int v = 0;

				for(int j = 1;j <= n; ++j) {

					if(ii & c2[j - 1]) v += c[j - 1];

					if(i & c2[j - 1]) v += c[j - 1];

				}

				if(f[v]) {

					for(int j = 1;j <= n; ++j) {

						if(v / c[j - 1] % 3 == 0) {

							int V = v + 2 * c[j - 1];

							for(int k = j + 1;k <= n; ++k) {

								if(V / c[k - 1] % 3 == 2) {

									V -= c[k - 1];

									break;

								}

							}

							f[V] += f[v];

						}

					}

				}

				if(ii == 0) break;

			}

		}

	}

	dfs(1,m,0);

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

	return 0;

}

巴特西

[JZOJ 5600] Arg

最新文章

热门文章