现在的位置: 首页 > 综合 > 正文

HDU 4352 XHXJ’s LIS(数位DP)

2018年10月12日 ⁄ 综合 ⁄ 共 1182字 ⁄ 字号 评论关闭

这题跟常规的数位DP有所不同,因为样历数很多,所以不能每次都完整的状态DP一边,先说一下状态dp[i][s]表示i位,lis状态为s的状态,根据这个状态去转移,为了不每次都清空一次,对于每种k,在开一维,然后dp数组的含义变成,i位数字,状态s,要求k的答案,那么记忆化搜的时候,遇到小于的情况,就可以直接记忆化搜索,这样等于只需要在完全等于原数的一条路径上进行搜索即可

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

int t, k;
ll l, r;

int bit[25], bn;

int bitcount(int x) {
	if (x == 0) return 0;
	return bitcount(x>>1) + (x&1);
}

void get(ll x) {
	bn = 0;
	if (!x) bit[bn++] = 0;
	while (x) {
		bit[bn++] = x % 10;
		x /= 10;
	}
}

ll dp[25][1025][11];

int getnext(int s, int x) {
	int flag = 1;
	if (x == 0 && s == 0) return 0;
	for (int i = 0; i < 10; i++) {
		if (s&(1<<i) && x <= i) {
			s ^= (1<<i);
			s ^= (1<<x);
			flag = 0;
			break;
		}
	}
	if (flag) s ^= (1<<x);
	return s;
}

int to[1025][10], bitc[1024];

ll dfs(int u, int s, int k, int flag) {
	if (u == -1)
		return bitc[s] == k;
	ll &ans = dp[u][s][k];
	if (ans != -1 && flag) return ans;
	ll tmp = 0;
	int end = flag ? 9 : bit[u];
	for (int i = 0; i <= end; i++) {
		if (i < bit[u]) tmp += dfs(u - 1, to[s][i], k, 1);
		else tmp += dfs(u - 1, to[s][i], k, flag);
	}
	if (flag) ans = tmp;
	return tmp;
}

ll solve(ll x) {
	get(x);
	return dfs(bn - 1, 0, k, 0);
}

int main() {
	int cas = 0;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < 1024; i++) {
		bitc[i] = bitcount(i);
		for (int x = 0; x < 10; x++)
			to[i][x] = getnext(i, x);
	}
	scanf("%d", &t);
	while (t--) {
		scanf("%I64d%I64d%d", &l, &r, &k);
		printf("Case #%d: %I64d\n", ++cas, solve(r) - solve(l - 1));
	}
	return 0;
}

抱歉!评论已关闭.