ICPCCamp 2016 Data structure you've never heard of
? 解题记录 ? ? 动态规划 ? ? 状态压缩 ?    2018-08-25 08:46:11    928    0    0

【题目描述】

给你n个k维0/1向量组成的串a[n]。

定义向量a <= b当且仅当a中每一个1出现的位置在b中都是1

比如{0,1,0,1}<={0,1,0,1}, {0,1,0,1}<={0,1,1,1}

但是{0,1,0,1}和{1,0,0,1}没有这样的关系

现在请你统计这个串中有多少个不下降子序列。

一个子序列是一个1~n组成的序列,

其中每个元素都满足i < j且a[i] <= a[j]。

【输入】

第一行两个正整数n,k。n表示串的长度,k表示向量维数

下面n行每一行一个0/1字符串表示一个k维向量

【输出】

输出一个整数,表示不下降序列个数。

【输入样例】

2 2
01
11

【输出样例】

3

【提示】

对于30%的数据,n5000n≤5000

对于100%的数据,n100000,k16

神奇的题,首先考虑O(N^2)的DP,是简单的,就是把之前所有比他小的DP值加起来再加1。能不能像最长上升子序列一样用一个数据结构维护[之前所有比他小的DP值加起来]呢?但是2^16卡不过去。考虑把16位分为前8位和后8位。我们用DS[mask1][mask2]表示之前前8位是[mask1],后8位是[mask2]子集的a[i]对应位置上的DP和。

考虑这个结构,我们修改是O(2^8)枚举后8位,查询是O(2^8)枚举前8位。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define SubSet(i, a) for(register int i = a; i; i = (i - 1) & a)
#define SuperSet(i, a) for(register int i = a; i < ST; i = (i + 1) | a)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int B = 8, ST = 1 << B;
int dp[maxn], n, ans;
int DS[ST + 5][ST + 5], lowmask, topmask;
int a[maxn], b, tmp;
char s[25];

void AddMod(int &x, int y) {
	x += y;
	if(x >= mod) x -= mod;
}

void add(int x, int w) {
	tmp = (x & topmask) >> B;
	SuperSet(i, (x & lowmask)) AddMod(DS[tmp][i], w);	
}

int query(int x) {
	int ans = 0;
	tmp = (x & lowmask);
	SubSet(i, (x & topmask) >> B) 
		AddMod(ans, DS[i][tmp]);
	AddMod(ans, DS[0][tmp]);
	return ans;
}

int main() {
	scanf("%d%d", &n, &b);
	lowmask = ST - 1;
	topmask = (ST - 1) << B;
	For(i, 1, n) {
		scanf("%s", s);
		For(j, 0, b - 1) 
			a[i] = a[i] * 2 + (s[j] == '1');
	}
	ans = dp[1] = 1, add(a[1], 1);
	For(i, 2, n) {
		dp[i] = query(a[i]) + 1;
		add(a[i], dp[i]);
		AddMod(ans, dp[i]);
	}
	printf("%d", ans);
	return 0;
}

上一篇: 炉石传说中的期望

下一篇: HDU4135 Co-prime

928 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航