HDU4352 XHXJ's LIS 数位DP+状态压缩

3/3/2017来源:C/C++教程人气:1561

题目链接: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; }