黄山新洲建设集团网站,微软做网站的软件,做个企业网站,徐州网站建设市场分析题目 思路 也是一道比较典型的数位dp的问题#xff0c;关键的思想跟我上一篇博客很像#xff0c; 首先把区间值变成[1,Y]-[1,X-1]的值#xff0c;然后单独计算得到结果。 总的来说就是把这个数的每一位都单独拿出来#xff0c;然后根据选0-an-1和选**an**两种方案单独计算关键的思想跟我上一篇博客很像 首先把区间值变成[1,Y]-[1,X-1]的值然后单独计算得到结果。 总的来说就是把这个数的每一位都单独拿出来然后根据选0-an-1和选**an**两种方案单独计算
当选第一种方案时就是后面的i位**因为最低为从a0开始的数字可以任意选那么就可以表示为前面的最高位为last**一共i1位的决策数。 ps上一篇博客的图
那么这里求决策数就需要用到动态规划了。 这里用f[i][j]表示前面的最高位为j并且一共有i位的不降数的集合 那么f[i][j]肯定要从前面的状态中得到那么在第i位为j的时候 i-1位的选择可以为 j , j 1 , j 2 … 9这些情况 这些情况之和就相当于f[ i ] [ j ] , 那么f [ i ] [ j ]就可以表示为f[ i -1] [ j ]f [ i-1 ] [ j 1 ]…f [ i -1] [ 9 ]。这里可以预处理获得所有情况的f[ i ] [ j ]这样上面的方案数就可以直接算出来了这里借用了y总的图片一用 当选第二种方案时 即要选择当前位的最大值时要进行特判即上一位的最大值是不是小于当前位的最大值的即lastx如果不满足则不能走到下一位直接返回如果满足则直接进行最大值的覆盖。然后走到最右下角的决策时如果还是能选到a0那么就作为一种方案数使res然后返回res即可。
具体代码
#includecstdio
#include iostream
#include algorithm
#include string.h
#include string
#include math.h
#includevector
#includequeue
#includemap
#define sc_int(x) scanf(%d, x)
#define sc_ll(x) scanf(%lld, x)
#define pr_ll(x) printf(%lld, x)
#define pr_ll_n(x) printf(%lld\n, x)
#define pr_int_n(x) printf(%d\n, x)
#define ll long long
using namespace std;const int N20;
int n ,m,h;
int s[N][N];void cal()
{for(int i 0;i9;i)s[1][j]1;for(int i 1;iN;i)for(int j 0;j9;j)for(int kj;k9;k)s[i][j]s[i-1][k];
}int dp(int n)
{if(!n) return 1;//特判如果为0也可以作为一种决策vectorintcnt;while(n)cnt.push_back(n%10),n/10;int res0;int last0;for(int i cnt.size()-1;i0;i--){int xcnt[i];for(int j last;jx;j)ress[i1][j];if(lastx)break;xlast;if(!i)res;}return res;
} int main()
{int t;cal();int l,r;while(cinlr)coutdp(r)-dp(l-1)endl;return 0;
}ps作为数位dp的第二篇感觉理解起来容易了很多最不好理解的点还是方案数的预处理哪里希望以后的数位dp能越学越熟悉吧。
