【HDU4734】F(x) 数位DP

题目描述

　　For a decimal number x with n digits (A[n]A[n-1]A[n-2] … A[2]A[1]), we define its weight as F(x) = A[n] * 2^(n-1) + A[n-1] * 2^(n-2) + … + A[2] * 2 + A[1] * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

题目大意

　　对于一个数字x，n为x的位数，ai为从右往左第i位的数字。f(x)=∑ni=12i−1∗a[i]，给定数字A，B，求在0-B中这B+1个数中，f(x) < f(A) 的x个数。

数据范围

(0 <= A,B < 10^9)

样例输入

3
0 100
1 10
5 100

样例输出

Case #1: 1
Case #2: 2
Case #3: 13

解题思路

数位DP
太水了就不写具体了qwq

代码

#include <bits/stdc++.h> using namespace std; inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} int A,B,Max,lim[15]; int dp[3005][15]; void f(int x){int Len=0,ret=0;while(x)ret+=(x%10)*(1<<Len++),x/=10;Max=ret; } int Ask(int pos,int Sum,bool flag){if(!pos)return Sum<=Max;if(!flag&&~dp[Sum][pos])return dp[Sum][pos];int bound=flag?lim[pos]:9,ret=0;for(int i=0;i<=bound;i++)ret+=Ask(pos-1,Sum+(1<<pos-1)*i,flag&&i==bound);return !flag?dp[Sum][pos]=ret:ret; } int Ask(int x){int Len=0;while(x){lim[++Len]=x%10;x/=10;}return Ask(Len,0,1); } int main(){int Case=Getint();for(int i=1;i<=Case;i++){memset(dp,-1,sizeof(dp));f(Getint());cout<<"Case #"<<i<<": "<<Ask(Getint())<<"\n";}return 0; }

转载于:https://www.cnblogs.com/Cedric341561/p/6810989.html

总结

以上是生活随笔为你收集整理的【HDU4734】F(x) 数位DP的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。