首页 > 代码库 > hdu4352（数位dp）
hdu4352（数位dp）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4352
题意：求区间L到R之间的数A满足A的的数位的最长递增序列的长度为K的数的个数。
分析：数位dp，dp[i][j][k]表示后面还有i位，此时状态为k，最长上升子序列为j时的总数（在非限制即0~9任意填的情况下）。
要真正理解LIS的本质才能解这题，state状态维护的是前面上升子序列中出现的数字（二进制状态压缩），前面设状态为167（state为001100001），假设此时i=2，维护上升序列长度为3，应该把6变为2（此时state为001000011）127，最长上升子序列长度不变，但能让后面更多的数加进来。
这题还得注意前导0的影响。
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dig[30];LL dp[25][11][1100];int k;//当前位，上升子序列出现的数字的状态，长度，是否上限，是否前导0LL dfs(int pos,int state,int num,int limit,int fzore){ if(!pos) { return k==num; } if(!limit&&~dp[pos][k][state])return dp[pos][k][state]; int len=limit?dig[pos]:9; LL ans=0; for(int i=0;i<=len;i++) { if((1<<i)>state) ans+=dfs(pos-1,(fzore&&!i)?0:state|(1<<i),(fzore&&!i)?0:num+1,limit&&i==len,fzore&&!i); else if(state&(1<<i)) ans+=dfs(pos-1,state,num,limit&&i==len,fzore&&!i); else { for(int j=i+1;j<=9;j++) if(state&(1<<j)) { ans+=dfs(pos-1,state-(1<<j)|(1<<i),num,i==len&&limit,fzore&&!i); break; } } } if(!limit)dp[pos][k][state]=ans; return ans;}LL solve(LL x){ int len=0; while(x) { dig[++len]=x%10; x/=10; } return dfs(len,0,0,1,1);}int main(){ int T,cas=1; FILL(dp,-1); scanf("%d",&T); while(T--) { LL a,b; scanf("%I64d%I64d%d",&a,&b,&k); printf("Case #%d: ",cas++); printf("%I64d\n",solve(b)-solve(a-1)); }}
hdu4352（数位dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。