一道状压，数位dp的题目（XHXJ's LIS）

Question

传送门 https://acm.hdu.edu.cn/showproblem.php?pid=4352
①用state记录状压后的这个数转换的字符串数组的情况，通过bitset来转换状态
②剩下的就是数位dp的板子了
debug了一个小时 没找到问题

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll int maxn = 120;
const ll int N = 1e5+10;
#define bug(x) cout<<#x<<"=="<<x<<endl;
int dp[30][3000][30] = { 0 };
int a[30] = { 0 };
int pos = 0;
int k;
inline bool check(int x)
{
    bitset<15> bits = x;
    return bits.count()==k;
    ///数组里面有多少个1
}
inline int get_next(int state,int now)
{
    bitset<15> bits=state;
    int i=now;
    for(; i<=9; i++)
    {
        if(bits[i]==1)
        {
            break;
        }
    }
    if(i!=10)
    {
        bits[i] = 0;
    }
    bits[now]=1;
    ///修改最长序列的末尾值
    int ans=bits.to_ulong();
    ///讲二进制的数组转换成unsigned long的整数型
    return ans;
}
int dfs(int pos,int state,bool lead,bool limit)
{
    if(!pos)
    {
        return check(state);
    }
    if( (!limit&&!lead) &&dp[pos][state][k]!=-1)
    {
        return dp[pos][state][k];
    }
    int up=9;
    if(limit)
    {
        up=a[pos];
    }
    int ans = 0;
    for(int i=0; i<=up; i++)
    {
        if(lead&& i==0 )
        {
            ans += dfs(pos-1,state,lead&& i==0,limit&&i==a[pos]);
        }
        else
        {
            int next_state=get_next(state,i);
            ans += dfs(pos-1,next_state,lead&& i==0,limit&&i==a[pos]);
        }
    }
    if(!limit&&!lead)
    {
        dp[pos][state][k] = ans;
    }
    return ans;
}
int slove(ll x)
{
    if(x==0)return 0;
    pos = 0;
    while(x)
    {
        pos++;
        a[pos] = x%10;
        x /= 10;
    }
    int ans=dfs(pos,0,true,true);
    if(ans==0)
        return 0;
    return ans;
}
signed main()
{
    ll l,r;
    int T_T;
    scanf("%d",&T_T);
    memset(dp,-1,sizeof(dp));
    int tot=0;
    while(T_T--)
    {
        tot++;
        cin>>l>>r>>k;
        printf("Case #%d: ",tot);
        cout<<slove(r)-slove(l-1)<<'\n';
    }
}

Answer 1

如果我的回答对你有帮助，请采纳我的回答，谢谢

思路：
本来想的是维护一个num[10]，num[i]表示以i结尾的lis的长度，0<=num[i]<=9。然后状态压缩的时候发现压缩后太大，看了题解之后知道，必须要用nlogn求lis的思路来做，因为nlogn的思路是维护一个长度为10的bool数组，压缩后状态数少很多。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7f7f7f7f
#define LL long long
LL dp[20][1<<10][11];
int k,t;
int bit[20];

int update(int x,int s)
{
    for(int i=x;i<10;i++)
    {
        if(s&(1<<i))
            return (s^(1<<i))|(1<<x);
    }
    return s|(1<<x);
}

int getK(int s)
{
    int cnt = 0;
    while(s)
    {
        if(s&1) cnt++;
        s >>= 1;
    }
    return cnt;
}

LL dfs(int pos,int s,bool e,bool z)
{
    if(!pos) return getK(s)==k;
    if(!e&&dp[pos][s][k]!=-1) return dp[pos][s][k];
    int digit=e?bit[pos]:9;
    LL ans=0;
    for(int i=0;i<=digit;i++)
        ans+=dfs(pos-1,(z&&(i==0))? 0:update(i,s),e&&i==digit,z&&(i==0));
    if(!e) dp[pos][s][k]=ans;
    return ans;
}

LL solve(LL n)
{
    int len = 0;
    while(n)
    {
        bit[++len] = n%10;
        n /= 10;
    }
    return dfs(len,0,1,1);
}

int main()
{
    cin>>t;
    int cas = 1;
    memset(dp,-1,sizeof dp);
    while(t--)
    {
        LL a,b;
        cin>>a>>b>>k;
        printf("Case #%d: %I64d\n",cas++,solve(b)-solve(a-1));
    }
    return 0;
}

或

/*
 * HDU 4352 XHXJ's LIS
 * 问L到R，各位数字组成的严格上升子序列的长度为K的个数。
 * 0<L<=R<263-1 and 1<=K<=10
 * 注意这里最长上升子序列的定义，和LIS是一样的，不要求是连续的
 * 所以用十位二进制表示0~9出现的情况，和O(nlogn)求LIS一样的方法进行更新
 * 
 */

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
long long dp[25][1<<10][11];
/*
 * dp[i][j][k]:i为当前进行到的数位，j状态压缩，为10个数字出现过的，其中1的个数就是最长上升子序列，k要求的上升子序列的长度
 */
int K;
int getnews(int x,int s)//更新新的状态
{
    for(int i=x;i<10;i++)
        if(s&(1<<i))return (s^(1<<i))|(1<<x);
    return s|(1<<x);
}
int getnum(int s)//得到状态s中1的个数
{
    int ret=0;
    while(s)
    {
        if(s&1)ret++;
        s>>=1;
    }
    return ret;
}
int bit[25];
long long dfs(int pos,int s,bool e,bool z)//e是是不是上界标记，z是是不是前面的为0标记
{
    if(pos==-1)return getnum(s)==K;
    if(!e &&dp[pos][s][K]!=-1)return dp[pos][s][K];
    long long ans=0;
    int end=e?bit[pos]:9;
    for(int i=0;i<=end;i++)
        ans+=dfs(pos-1,(z&&i==0)?0:getnews(i,s),e&&i==end,z&&(i==0));
    if(!e)dp[pos][s][K]=ans;
    return ans;
}
long long calc(long long n)
{
    int len=0;
    while(n)
    {
        bit[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,0,1,1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    long long l,r;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T);
    int iCase=0;
    while(T--)
    {
        iCase++;
        scanf("%I64d%I64d%d",&l,&r,&K);
        printf("Case #%d: ",iCase);
        printf("%I64d\n",calc(r)-calc(l-1));
    }
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int dp[20][1300][20];
int len;
int dig[20];
const int mod = 1e9+7;
int get_next(int state,int x){
    bitset<10>bit = state;
    int i;
    for(i = x;i <= 9;i ++){
        if(bit[i]==1) break;
    }
    if(i!=10) bit[i] = 0;
    bit[x] = 1;
    int ans  = bit.to_ulong();
    return ans;
}
bool check(int state,int k){
    bitset<10>bit = state;
    if(bit.count()==k) return 1;
    else return 0;
}
ll dfs(int pos,int state,int k,bool zero,bool limit){
    if(pos==0) return check(state,k);
    if(!limit&&dp[pos][state][k]!=-1&&!zero) return dp[pos][state][k];
    int i;
    int up = limit?dig[pos]:9;
    ll ans=0;
    for(i = 0;i <= up;i ++){
        if(zero&&i==0){
            ans += dfs(pos-1,state,k,zero&&i==0,limit&&i==up);
            continue;
        }
        int next = get_next(state,i);
        ans += dfs(pos-1,next,k,zero&&i==0,limit&&i==up);
    }
    if(!limit&&!zero)dp[pos][state][k] = ans;
    return ans;
}
ll solve(ll n,int k){
    if(n==-1) return 0;
    len = 0;
    while(n!=0){
        dig[++len] = n%10;
        n /= 10;
    }
    return dfs(len,0,k,1,1);
}
int main()
{
    freopen("a.txt","r",stdin);
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    memset(dp,-1,sizeof(dp));
    int tot = 0;
    while(T--){
        tot ++;
        ll l,r;
        int k;
        cin>>l>>r>>k;
        cout<<"Case #"<<tot<<": ";
        cout<<solve(r,k)-solve(l-1,k)<<endl;
    }
    return 0;
}