题目链接：http://acm.hdu.edu.cn/showPRoblem.php?pid=4352 题意：假设把一个数字当成字符串，将它的最长单调递增子序列长度称为power值，求[L,R]区间内power值等于k（1<=K<=10）的值有多少个。 想法：很明显是数位DP，只是单调递增子序列状态压缩稍微麻烦点，单调递增子序列的nlogn解法是另开一个dp数组，在dp数组中将最长的单调递增序列存进去，并不断更新，在更新过程中dp数组始终是单调递增（不是非单调递减）的，所以我们可以将整个序列用二进制来表示，如：1 4 5的序列可以表示为(1<<1)+(1<<4)+(1<<5)，即50来表示。另状态转移时也需留意一下，处理起来也不算太麻烦。 整个dp[i][j][k]表示长度为i位，状态为j，power值为k时，存在多少个数字。 代码：
#include<map>#include<stack>#include<string>#include<cstdio>#include<cmath>#include<queue>#include<vector>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define ll long long#define inf 0x3f3f3f3f#define bug() puts("wtf???")#define mem(a,b) memset(a,b,sizeof(a))#define s_print() freopen("input.txt","r",stdin)#define p_print() freopen("output.txt","w",stdout)const int mod=1e9+7;const int spot=1000+10;const double pi=acos(-1.0);const int edge=100000+10;const int maxn=100000+10;const double ips=0.000001;ll dp[21][(1<<10)+1][11],lis[(1<<10)+1],a[21];//lis[]提前打表，对应此状态的power值void init()//提前打表{ for(int i=0; i<(1<<10); i++) { int t_i=i; while(t_i) //二进制位中1的个数即为其power值 { lis[i]++; t_i&=(t_i-1); } } memset(dp,-1,sizeof(dp));}int g_new(int sta,int i) //状态转移，即sta的递增子序列中添加一个i{ if(!sta&&!i) return 0; //避免前导0 int j=0; if(sta<=(1<<i)) //若i大于sta状态中的最大值，直接在sta后添加上i即可（等于也无所谓） sta|=(1<<i); else for(j=i; j<=9; j++) //若i小于sta状态中的最大值，则从i开始寻找子序列中大于i的值，并替换它即可 { if(sta&(1<<j)) { sta^=(1<<j); //去掉子序列中大于i的值， sta|=(1<<i);//替换 break; } } return sta;}ll dfs(int pos,int sta,ll k,int last){ if(!pos) return lis[sta]==k?1:0; if(!last&&dp[pos][sta][k]!=-1) return dp[pos][sta][k]; int i,num=last?a[pos]:9,t_sta; ll ans=0; for(i=0; i<=num; i++) { t_sta=g_new(sta,i); //状态转移 ans+=dfs(pos-1,t_sta,k,last&&i==num); } if(!last) dp[pos][sta][k]=ans; return ans;}ll cal(ll n,ll k){ int len=0; while(n) a[++len]=n%10,n/=10; return dfs(len,0,k,1);}int main(){ int nn,i,j,casen=0; scanf("%d",&nn); init(); while(nn--) { ll l,r,k; cin>>l>>r>>k; printf("Case #%d: ",++casen); cout<<cal(r,k)-cal(l-1,k)<<endl; } return 0;}新闻热点
疑难解答
