2020牛客暑期多校训练营第六场Harmony Pairs（数位dp）

题目

传送门

题目大意

分析

这题N非常大（10100）果断放弃暴力，又由各位数字和想到数位dp，于是经过一些魔改便能快乐AC：

int DFS(int pos,int diff,bool l1,bool l2)//pos记录当前位数，diff记录A与B的差，l1,l2分别记录A的高位与B是否相同，B的高位与N是否相同{if(!pos) return diff>1000;//A，B差值可能为负，要加1000的偏移量int ret=0;if(~dp[pos][diff][l1][l2]) return dp[pos][diff][l1][l2];//记忆化for(int i=0;i<=(l2?a[pos]:9);i++)//（l2?a[pos]:9）表示若高位相同，又因为B 小于N，则B的取值范围为[0,a[pos]]，若高位不相同则[0,9]随便选（反正高位已经比N小了），下同{for(int j=0;j<=(l1?i:9);j++){ret=(ret+DFS(pos-1,diff+j-i,l1&(i==j),l2&(i==a[pos])))%mod;}}return dp[pos][diff][l1][l2]=ret;}

代码

#include <bits/stdc++.h>using namespace std;const int MAXN=111,mod=1e9+7;int len,a[MAXN],dp[MAXN][MAXN*20][2][2];char s[MAXN];int DFS(int pos,int diff,bool l1,bool l2){if(!pos) return diff>1000;int ret=0;if(~dp[pos][diff][l1][l2]) return dp[pos][diff][l1][l2];for(int i=0;i<=(l2?a[pos]:9);i++) for(int j=0;j<=(l1?i:9);j++) ret=(ret+DFS(pos-1,diff+j-i,l1&(i==j),l2&(i==a[pos])))%mod;return dp[pos][diff][l1][l2]=ret;}int main(){memset(dp,-1,sizeof dp);scanf(\"%s\",s);len=strlen(s);for(int i=0;i<len;i++) a[len-i]=s[i]-\'0\';printf(\"%d\\n\",DFS(len,1000,1,1));}