zoj 3962 Seven Segment Display 数位dp

非常好的一个题，可以比赛时想到的状态太奇葩，不方便转移，就一直没能AC。

思路：dp(i, j)表示已经考虑了前i位，前i位的和为j的贡献。如果当前的选择一直是最大的选择，那么就必须从0~下一位的最大值之间选择，所以必须增加一个标记表示当前是否被限制。否则就可以从0~15中任选一个填充该位，这种情况就是可能被重复访问的，因为要填充剩下的位，每一位都能填0~15，所以记忆一下，当再次访问时就返回。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 8 + 5;
const LL mod = (LL)0xffffffff+1;
const int w[] = {6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4};
LL dp[maxn][maxn*7];
LL a[maxn];
LL dfs(int pos, int sum, int flag) {
	if(pos < 0) return sum;
	if(!flag && dp[pos][sum] != -1) return dp[pos][sum];
	int n = flag ? a[pos] : 15;
	LL ans = 0;
	for(int i = 0; i <= n; ++i)
		ans += dfs(pos-1, sum+w[i], flag&&(i==n));
	if(!flag) dp[pos][sum] = ans;
	return ans;
}

LL solve(LL x) {
	if(x < 0) return 0;
	memset(a, 0, sizeof(a));
	int cur = 0;
	while(x > 0) {
		a[cur++] = x % 16;
		x /= 16;
	}
	return dfs(7, 0, 1);
}

LL get(char *s) {
	LL res = 0;
	LL v = 1;
	for(int i = 7; i >= 0; --i) {
		if(s[i] >= 'A' && s[i] <= 'F') {
			res += (s[i] - 'A' + 10) * v;
		}
		else res += (s[i] - '0') * v;
		v *= 16;
	}
	return res;
}

int main() {
	memset(dp, -1, sizeof(dp));
	int T;
	scanf("%d", &T);
	LL n;
	char s[10];
	while(T--) {
		scanf("%lld%s", &n, s);
		LL res = get(s);
		--n;
		if(res + n >= mod) {
			printf("%lld\n", solve((res+n)%mod) + solve(mod-1) - solve(res-1));
		}
		else printf("%lld\n", solve(res+n) - solve(res-1));
	}
	return 0;
}

如有不当之处欢迎指出！

巴特西

zoj 3962 Seven Segment Display 数位dp

最新文章

热门文章