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

状态压缩 DP，数位 DP P1433 吃奶酪 设 dp_{i,j} 表示当前选择的集合为 i 时，最后一个拿到的奶酪为 k，所走的最小距离，就可以枚举最后一个点和走到的新点进行转移，复杂度 O(2^nn^2)。 代码： 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 卷] 滚榜 题目要求的是排列的方案数，所以我们不需要求出具体的 b_i，考虑记录其差分数组，每次加上对后面的影响，并且转移时贪心地按照最优策略转移。 代码： 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 模板题，先枚举模数， 设 dp_{p,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; }`