[51Nod1623] 完美消除

$solution:$

首先我们可以发现一个结论，对于一个数 $x$ ，它的最低修改次数为它每位与前去中是否都比此位上的数大，有则答案 $-1$ 。因为若有小数则没有办法将其答案贡献变低。

这个东西可以直接单调栈维护一个递增序列。

所以这样 $dp$ 状态也很显然了，设 $f_{i,j,sta}$ 表示当前到 $i$ 位，答案为 $j$ ，$sta$ 表示当前栈中 $0-9$ 是否在栈中。

简单数位转移即可。

时间复杂度 $O(10\times 18^2 \times 2^{10})$ 。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define int long long

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int dig[],f[MAXN][MAXN][<<];

int l,r,k,cnt;

void debug(int sta){

    int Dig[];

    Dig[]=;

    while(sta){

        Dig[++Dig[]]=sta%;

        sta/=;

    }

    for(int i=Dig[];i>=;i--) printf("%d ",Dig[i]);printf("\n");

    return ;

}

int dfs(int ps,int K,int sta,int done){

    if(!done&&f[ps][K][sta]!=-) return f[ps][K][sta];

    if(ps==){

        if(K==k) return ;

        return ;

    }

    int end,Ans=;

    if(done) end=dig[ps];

    else end=;

    for(int i=;i<=end;i++){

        int S=sta;

        for(int j=i+;j<=;j++) if(S&(<<j)) S-=(<<j);

        if(S&(<<i)) Ans+=dfs(ps-,K,S,done&(i==dig[ps]));

        else Ans+=dfs(ps-,K+,S+(<<i),done&(i==dig[ps]));

    }

    if(done==) f[ps][K][sta]=Ans;

    return Ans;

}

int solve(int x){

    dig[]=;

    while(x){

        dig[++dig[]]=x%;

        x/=;

    }

    return dfs(dig[],,,);

}

signed main(){

    freopen("digit.in","r",stdin);

    freopen("digit.out","w",stdout);

    memset(f,-,sizeof(f));

    l=read(),r=read(),k=read();

    printf("%lld\n",solve(r)-solve(l-));return ;

}

巴特西

[51Nod1623] 完美消除

$solution:$

最新文章

热门文章