【HDU4352】XHXJ's LIS 数位DP

题目描述

题目太长还是英文。。。要看去HDU上看吧

题目大意

求L-R中，LIS为k的个数

数据范围

(0 < L<=R<2^63-1 and 1 <= K <= 10).

样例输入

1
123 321 2

样例输出

Case #1: 139

解题思路

最开始读错题了英语差qwq，然后错了很多次。

代码

#include <bits/stdc++.h>
using namespace std;
inline long long Getll(){long long 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 lim[25],k;
long long dp[25][1300];
long long Ask(int pos,int s,int Max,bool flag){
    if(!pos)return Max==k;
    if(!flag&&~dp[pos][s])return dp[pos][s];
    int bound=flag?lim[pos]:9;
    long long ret=0;
    for(int i=0;i<=bound;i++)
        if(s+i==0)ret+=Ask(pos-1,s,Max,0);
        else if((1<<i)>s)ret+=Ask(pos-1,s|(1<<i),Max+1,flag&&(i==bound));
        else if((1<<i)&s)ret+=Ask(pos-1,s,Max,flag&&(i==bound));
        else for(int j=i+1;j<=9;j++)
            if((1<<j)&s){
                ret+=Ask(pos-1,s-(1<<j)+(1<<i),Max,flag&&(i==bound));
                break;
            }
    return !flag?dp[pos][s]=ret:ret;
}
long long Ask(long long x){
    if(!x)return 0;
    int Len=0;
    while(x){lim[++Len]=x%10;x/=10;}
    return Ask(Len,0,0,1);
}
int main(){
    int Case=Getll();
    for(int i=1;i<=Case;i++){
        memset(dp,-1,sizeof(dp));
        long long L=Getll(),r=Getll();
        k=Getll();
        cout<<"Case #"<<i<<": "<<Ask(r)-Ask(L-1)<<"\n";
    }
    return 0;
}