首页 > 代码库 > Hdu4352XHXJ's LIS数位dp

Hdu4352XHXJ's LIS数位dp

2024-07-16 11:36:58   214人阅读

nlogn 的 最长上升子序列的求法。   用一个数的二进制位来表示哪几位有值， 每次插入的时候 ，要把在他后方位置的第一个数给删了。 设 从前到后 他是第i个数，长度为i的最长上升子序列的最后一位最小的值就是他在这个数中二进制所在的位置。  注意处理 0，  前面是0  ，是不能乱插的。

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;typedef long long LL;LL dp[44][1<<10][44];LL up[1000];LL gao2[1<<10];LL goal;LL gao(LL x,LL cha){    if(x&(1<<cha)) return x;    x|=(1<<cha);    for(LL i = cha+1;i<10;i++)    if(x&(1<<i)){        x&=~(1<<i);        break;    }    return x;}LL gao1(LL x){    LL ans=0 ;    while(x){        if(x&1) ans++;        x>>=1;    }    return ans;}LL dfs(LL now,LL pre,LL first,LL flag ){    LL sum = gao2[pre];    if(now<=0) return sum==goal;    if(!flag&&~dp[now][pre][goal]) return dp[now][pre][goal];    LL limit = flag? up[now] : 9,ret=0;    for(LL i =0 ;i<=limit;i++){        LL kk= gao(pre,i);       // cout<<pre<<" "<<i<<" "<<gao(pre,i)<<endl;system("pause");        ret+=dfs(now-1,(first&&i==0)?0:kk,first&&i==0,flag&&i==limit);//前导0  是不能插的 。。。。  。。 。 。 。    }    return flag? ret: dp[now][pre][goal] = ret ;}LL solve(LL x){    LL len=0;    while(x){        up[++len]= x%10;        x/=10;    }    return dfs(len,0,1 ,1) ;}int main(){    LL Icase;LL a;LL b;    memset(dp,-1,sizeof(dp));    for(LL i =0 ;i<(1<<10) ;i++){        gao2[i]= gao1(i);    }    scanf("%d",&Icase);    for(LL i = 1;i<= Icase;i++){        cin>>a>>b;        cin>>goal;        printf("Case #%d: ",i);        cout<<solve(b) - solve(a-1) <<endl;    }    return 0;}

 


联系
我们