本文主要是介绍URAL 1057 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
数位DP
DP[i][j][k] 表示第i位 为j 选k个1 的方案数
转移方程
j > 1 DP[i][j][k] = 0;
j = 1 DP[i][j][k] = DP[i - 1][1][k - 1] + DP[i - 1][0][k - 1]
j = 0 DP[i][j][k] = DP[i - 1][1][k] + DP[i - 1][0][k]
初始化 DP[1][1][0] = 0,DP[1][1][1] = 1,DP[1][0][0] = 1,DP[1][0][1] = 0
构造解
pre_one 以确定1的个数,N 题目要求选择的1的个数
digit[i] = 1 : ans += DP[i][0][n - pre_one]
digit[i] = 0 : ans += 0
digit[i] > 1: ans += DP[i][0][n - pre_one] + DP[i][1][n - pre_one]
digit[i] > 1 之后直接退出迭代 因为这以后构造的解 都不能满足题意
代码如下：
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define sf scanf
#define pf printf
using namespace std;int digit[40];int get_digit(long long n,long long B){for(int i = 1;n;++i){digit[i] = n % B;n = n / B;if(!n) return i;}return 0;
}int dp[35][10][25];void init(){memset(dp,0,sizeof(dp));dp[1][0][0] = 1;dp[1][0][1] = 0;dp[1][1][0] = 0;dp[1][1][1] = 1;for(int i = 2;i < 35;++i){for(int k = 0;k <= i && k <= 20;++k){dp[i][0][k] = dp[i - 1][1][k] + dp[i - 1][0][k];dp[i][1][k] = dp[i - 1][1][k - 1] + dp[i - 1][0][k - 1];}}
}int get_f(long long x,int b,int n){int len = get_digit(x,b);int pre_one = 0,ans = 0;for(int i = len;i;--i){if(digit[i] > 1){ans += dp[i][0][n - pre_one];ans += dp[i][1][n - pre_one];return ans;}else if(digit[i] == 1){ans += dp[i][0][n - pre_one];}pre_one += ( digit[i] == 1 );if(pre_one == n){for(int j = i - 1;j;--j){if(digit[j] == 1) return ans + 1;}return ans;}}return ans;
}int main(){init();long long l,r;int b,n;while( sf("%lld%lld%d%d",&l,&r,&n,&b) != EOF ){pf("%d\n",get_f(r + 1,b,n) - get_f(l,b,n));}return 0;
}
这篇关于URAL 1057 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
