首页 > 代码库 > 20140712 classic 数位DP

20140712 classic 数位DP

2024-07-11 19:43:23   223人阅读

其实就是一道蛮简单的数位DP

考试的时候出了点小错导致基本Wa0 

还好数据分治有30分- -

num[i][j][k]表示前i位数字和为j的数的个数  k=0表示不顶上界  k=1表示顶上界

转移方程见代码

dp[i][j][k]表示前i位数字和为j的数的和

转移方程同见代码

 1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define mod 1000000007 5 typedef long long ll; 6  7 ll dp[60][600][2]; 8 ll num[60][600][2]; 9 int x,y;10 11 ll DP(char ch[60]) {12     memset(dp,0,sizeof(dp));13     memset(num,0,sizeof(num));14     int len=strlen(ch);15     int a[60];16     int sum[60];17     ll ans=0;18     sum[0]=0;19     for (int i=0;i<len;i++) {20         a[i+1]=(int)(ch[i])-48;21         sum[i+1]=sum[i]+a[i+1];22     }23     for (int j=0;j<a[1];j++) {24         dp[1][j][0]=j; num[1][j][0]=1;25     }26     dp[1][a[1]][1]=a[1]; num[1][a[1]][1]=1;27     for (int i=1;i<len;i++) {28         for (int j=0;j<600;j++) {29             if (j!=0 && dp[i][j][0]==0) continue;30             for (int k=0;k<10;k++) {31                 num[i+1][j+k][0]=(num[i+1][j+k][0]+num[i][j][0])%mod;32                 dp[i+1][j+k][0]=(dp[i+1][j+k][0]+dp[i][j][0]*10+k*num[i][j][0])%mod;33             }34         }35         if (sum[i]!=0 && dp[i][sum[i]][1]==0) continue;36         for (int k=0;k<a[i+1];k++) {37             num[i+1][sum[i]+k][0]=(num[i+1][sum[i]+k][0]+num[i][sum[i]][1])%mod;38             dp[i+1][sum[i]+k][0]=(dp[i+1][sum[i]+k][0]+dp[i][sum[i]][1]*10+k*num[i][sum[i]][1])%mod;39         }40         num[i+1][sum[i+1]][1]=(num[i][sum[i]][1]+num[i+1][sum[i+1]][1])%mod;41         dp[i+1][sum[i+1]][1]=(dp[i+1][sum[i+1]][1]+dp[i][sum[i]][1]*10+a[i+1]*num[i][sum[i]][1])%mod;42     }43     for (int j=x;j<=y;j++) ans=(ans+dp[len][j][0]+dp[len][j][1])%mod;44     return ans;45 }46 47 char l[60],r[60];48 49 int main() {50     scanf("%s",&l);51     scanf("%s",&r);52     scanf("%d%d",&x,&y);53     int len=strlen(l);54     len--;55     while (1) {56         if (l[len]==‘0‘) l[len]=‘9‘;57         else {58             l[len]=(char(int(l[len])-1));59             break;60         }61         len--;62         if (len==0) {63             for (int i=strlen(l)-1;i>0;i--) {64                 l[i-1]=l[i];65             }66             l[strlen(l)-1]=‘\n‘;67             break;68         }69     }70     ll R=DP(r);71     ll L=DP(l);72     while (R-L<0) R+=mod;73     printf("%lld",(R-L)%mod);74 }
View Code

 


联系
我们