ooliver

ZR 集训 Day9 - 状态压缩 DP，数位 DP

ooliver OI

状态压缩 DP，数位 DP

P1433 吃奶酪

设 dpi,j 表示当前选择的集合为 i 时，最后一个拿到的奶酪为 k，所走的最小距离，就可以枚举最后一个点和走到的新点进行转移，复杂度 O(2nn2)。

代码：

C++

#include
using namespace std;

int n;
double ans=1e9;
double x[25],y[25],dp[(1>n;
    for(int i=1;i>x[i]>>y[i];
    memset(dp,127,sizeof dp);
    for(int i=1;i>(j-1))&1)
            for(int k=1;k>(k-1))&1){
                dp[i][k]=min(dp[i][k],dp[i-(1

`#include
using namespace std;

int n;
double ans=1e9;
double x[25],y[25],dp[(115)+5][25];

double dis(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main(){
    cin>>n;
    for(int i=1;in;i++) cin>>x[i]>>y[i];
    memset(dp,127,sizeof dp);
    for(int i=1;in;i++) dp[1(i-1)][i]=dis(0,0,x[i],y[i]);
    for(int i=0;i(1n);i++)
        for(int j=1;jn;j++) if((i>>(j-1))&1)
            for(int k=1;kn;k++) if((i>>(k-1))&1){
                dp[i][k]=min(dp[i][k],dp[i-(1(k-1))][j]+dis(x[k],y[k],x[j],y[j]));
            }
    for(int i=1;in;i++) ans=min(ans,dp[(1n)-1][i]);
    printf("%0.2f",ans);
    return 0;
}`

P7519 [省选联考 2021 A/B 卷] 滚榜

题目要求的是排列的方案数，所以我们不需要求出具体的 bi，考虑记录其差分数组，每次加上对后面的影响，并且转移时贪心地按照最优策略转移。

代码：

C++

#include
using namespace std;

#define int long long
int n,m,x,id,ans;
int a[15],dp[(1>n>>m;
    for(int i=1;i>a[i];
        if(a[i]>x) x=a[i],id=i;
    }
    dp[0][0][0]=1;
    for(int i=1;i>i)&1)
            for(int j=0;j>j)&1)
                for(int v=max(0ll,a[j+1]-a[i+1]+(i>j))*(n-__builtin_popcount(s));vj))*(n-__builtin_popcount(s))];
                }
    for(int i=0;i

`#include
using namespace std;

#define int long long
int n,m,x,id,ans;
int a[15],dp[(113)+5][15][505];

signed main(){
    cin>>n>>m;
    for(int i=1;in;i++){
        cin>>a[i];
        if(a[i]>x) x=a[i],id=i;
    }
    dp[0][0][0]=1;
    for(int i=1;in;i++) if(n*max(a[id]-a[i]+(idi),0ll)m) dp[1(i-1)][i][n*max(a[id]-a[i]+(idi),0ll)]=1;
    for(int s=1;s(1n);s++)
        for(int i=0;in;i++) if(~(s>>i)&1)
            for(int j=0;jn;j++) if((s>>j)&1)
                for(int v=max(0ll,a[j+1]-a[i+1]+(i>j))*(n-__builtin_popcount(s));vm;v++){
                    dp[s|(1i)][i+1][v]+=dp[s][j+1][v-max(0ll,a[j+1]-a[i+1]+(i>j))*(n-__builtin_popcount(s))];
                }
    for(int i=0;im;i++) for(int j=1;jn;j++) ans+=dp[(1n)-1][j][i];
    coutans;
    return 0;
}`

P4127 [AHOI2009] 同类分布

数位 DP 模板题，先枚举模数，

设 dpp,s,m,y 表示当前数长度为 p、数位和为 s、数字取模为 m，y 表示有没有上界限制，这样情况下的答案，直接记忆化搜索。

代码：

C++

#include
using namespace std;

#define int long long
const int N=20;
int n,len,mod;
int a[N],dp[N][200][200][2];

int dfs(int p,int s,int m,int y){
    if(p>len) return (s==mod&&m==0);
    if(dp[p][s][m][y]!=-1) return dp[p][s][m][y];
    int mx=y?a[len-p+1]:9,res=0;
    for(int i=0;i>l>>r;
    cout

`#include
using namespace std;

#define int long long
const int N=20;
int n,len,mod;
int a[N],dp[N][200][200][2];

int dfs(int p,int s,int m,int y){
    if(p>len) return (s==mod&&m==0);
    if(dp[p][s][m][y]!=-1) return dp[p][s][m][y];
    int mx=y?a[len-p+1]:9,res=0;
    for(int i=0;imx;i++) res+=dfs(p+1,s+i,(m*10+i)%mod,i==mx&&y);
    return dp[p][s][m][y]=res;
}

int solve(int x){
    int res=0;
    len=0;
    while(x) a[++len]=x%10,x/=10;
    for(mod=1;mod9*len;mod++){
        memset(dp,-1,sizeof dp);
        res+=dfs(1,0,0,1);
    }
    return res;
}

signed main(){
    int l,r;
    cin>>l>>r;
    coutsolve(r)-solve(l-1);
    return 0;
}`

P3107 [USACO14OPEN] Odometer S

比较套路，枚举出现次数最多的那个数进行记忆化搜索即可。

注意会出现一个特例，就是一个数中有两个数字出现次数一样多，再做一遍记忆化把它容斥掉即可。

代码：

C++

#include
using namespace std;

#define int long long
const int N=20;
int len;
int a[N],dp[N][N][N][2][2];

int dfs1(int p,int k,int s1,int s2,int t1,int t2){
    if(p>len) return (s1>0&&s1>=s2);
    if(dp[p][s1][s2][t1][t2]!=-1) return dp[p][s1][s2][t1][t2];
    int mx=t1?a[len-p+1]:9,res=0;
    for(int i=0;ilen) return (s1>0&&s1==s2);
    if(dp[p][s1][s2][t1][t2]!=-1) return dp[p][s1][s2][t1][t2];
    int mx=t1?a[len-p+1]:9,res=0;
    if(x>l>>r;
    for(int i=0;i

`#include
using namespace std;

#define int long long
const int N=20;
int len;
int a[N],dp[N][N][N][2][2];

int dfs1(int p,int k,int s1,int s2,int t1,int t2){
    if(p>len) return (s1>0&&s1>=s2);
    if(dp[p][s1][s2][t1][t2]!=-1) return dp[p][s1][s2][t1][t2];
    int mx=t1?a[len-p+1]:9,res=0;
    for(int i=0;imx;i++) res+=dfs1(p+1,k,s1+(i!=0||t2==0)*(i==k),s2+(i!=0||t2==0)*(i!=k),i==mx&&t1,i==0&&t2);
    return dp[p][s1][s2][t1][t2]=res;
}

int dfs2(int p,int x,int y,int s1,int s2,int t1,int t2){
    if(p>len) return (s1>0&&s1==s2);
    if(dp[p][s1][s2][t1][t2]!=-1) return dp[p][s1][s2][t1][t2];
    int mx=t1?a[len-p+1]:9,res=0;
    if(xmx||t1==0) res+=dfs2(p+1,x,y,s1+(x!=0||t2==0),s2,x==mx&&t1,x==0&&t2);
	if(ymx||t1==0) res+=dfs2(p+1,x,y,s1,s2+(y!=0||t2==0),y==mx&&t1,y==0&&t2);
	if(x!=0&&y!=0&&t2==1) res+=dfs2(p+1,x,y,s1,s2,mx==0&&t1,t2);
    return dp[p][s1][s2][t1][t2]=res;
}

int s1(int num,int k){
    len=0;
    while(num) a[++len]=num%10,num/=10;
    memset(dp,-1,sizeof dp);
    return dfs1(1,k,0,0,1,1);
}

int s2(int num,int x,int y){
    len=0;
    while(num) a[++len]=num%10,num/=10;
    memset(dp,-1,sizeof dp);
    return dfs2(1,x,y,0,0,1,1);
}

signed main(){
    int l,r,ans=0;
    cin>>l>>r;
    for(int i=0;i9;i++) ans+=s1(r,i)-s1(l-1,i);
    for(int i=0;i9;i++) for(int j=i+1;j9;j++) ans-=s2(r,i,j)-s2(l-1,i,j);
    coutans;
    return 0;
}`

P9821 [ICPC 2020 Shanghai R] Sum of Log

依旧数位 DP，感觉也挺套路的，只不过是换成了二进制下的，其他好像没啥好说的了。

代码：

C++

#include
using namespace std;

#define int long long
const int N=32,mod=1e9+7;
int n,m;
int dp[N][2][2][2];

int dfs(int p,int t1,int t2,int t3){
    if(p>p)&1:1,m2=t2?(m>>p)&1:1,res=0;
    for(int i=0;i>T;
    while(T--){
        cin>>l>>r;
        cout

`#include
using namespace std;

#define int long long
const int N=32,mod=1e9+7;
int n,m;
int dp[N][2][2][2];

int dfs(int p,int t1,int t2,int t3){
    if(p0) return 1;
    if(dp[p][t1][t2][t3]!=-1) return dp[p][t1][t2][t3];
    int m1=t1?(n>>p)&1:1,m2=t2?(m>>p)&1:1,res=0;
    for(int i=0;im1;i++) for(int j=0;jm2;j++){
        if(i&j) continue;
        (res+=((t3&&(i||j))?(p+1):1)*dfs(p-1,(i==m1)&&t1,(j==m2)&&t2,t3&&!i&&!j))%=mod;
    }
    return (dp[p][t1][t2][t3]=res)%mod;
}

int solve(int x,int y){
    n=x,m=y;
    memset(dp,-1,sizeof dp);
    return (dfs(30,1,1,1)-1+mod)%mod;
}

signed main(){
    int T,l,r;
    cin>>T;
    while(T--){
        cin>>l>>r;
        cout(solve(l,r))%mod"\n";
    }
    return 0;
}`

P3413 SAC#1 - 萌数

需要想到一个点：长度大于或等于 2 的子串，其实我们只用判断两种情况：AA 和 ABA。

其余没什么特别的，注意 n 的范围很大。

代码：

C++

#include
using namespace std;

#define int long long
const int N=1005,mod=1000000007;
string l,r;
int n,a[N],dp[N][11][11][2];

int dfs(int pos,int l1,int l2,bool has,bool lim,bool lead){
    if(pos>n) return has;
    if(!lim&&!lead&&dp[pos][l1][l2][has]!=-1) return dp[pos][l1][l2][has];
    int mx=lim?a[pos]:9,res=0;
    for(int i=0;i>l>>r;
    int ans=(solve(r)-solve(l)+mod)%mod;
    if(check(l)) ans=(ans+1)%mod;
    cout

`#include
using namespace std;

#define int long long
const int N=1005,mod=1000000007;
string l,r;
int n,a[N],dp[N][11][11][2];

int dfs(int pos,int l1,int l2,bool has,bool lim,bool lead){
    if(pos>n) return has;
    if(!lim&&!lead&&dp[pos][l1][l2][has]!=-1) return dp[pos][l1][l2][has];
    int mx=lim?a[pos]:9,res=0;
    for(int i=0;imx;i++){
        if(lead&&!i) res=(res+dfs(pos+1,10,10,0,lim&&i==mx,1))%mod;
        else{
            bool nh=has;
            if(!lead){
                if(l1!=10&&i==l1) nh=1;
                if(l2!=10&&i==l2) nh=1;
            }
            res=(res+dfs(pos+1,i,l1,nh,lim&&i==mx,0))%mod;
        }
    }
    if(!lim&&!lead) dp[pos][l1][l2][has]=res;
    return res;
}

int solve(string s){
    n=s.size();
    for(int i=1;in;i++) a[i]=s[i-1]-'0';
    memset(dp,-1,sizeof(dp));
    return dfs(1,10,10,0,1,1);
}

bool check(string s){
    for(int i=0;is.size();i++){
        if(i+1s.size()&&s[i]==s[i+1]) return 1;
        if(i+2s.size()&&s[i]==s[i+2]) return 1;
    }
    return 0;
}

signed main(){
    cin>>l>>r;
    int ans=(solve(r)-solve(l)+mod)%mod;
    if(check(l)) ans=(ans+1)%mod;
    coutans"\n";
    return 0;
}`