好贷网好贷款

CodeForces 258B Little Elephant and Elections 数位DP

发布时间:2016-12-4 7:54:50 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"CodeForces 258B Little Elephant and Elections 数位DP",主要涉及到CodeForces 258B Little Elephant and Elections 数位DP方面的内容,对于CodeForces 258B Little Elephant and Elections 数位DP感兴趣的同学可以参考一下。

题意:有7个人要从m个数里面任选一个,且不能重复,一个数里面幸运数的个数就是4的个数加7的个数,求第一个人的这个数的幸运数的个数比其他六个人的幸运数之和还要大的方案数。 思路:先用数位DP求出幸运数长度为0~len的数分别有多少个,然后枚举第一个人的幸运数个数k,用一个深搜来求其他六个幸运数个数小于k的情况数。具体实现看代码: #include <cstdio> #include <cstring> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <cmath> #include <stack> #include <queue> #include <cstdlib> #include <algorithm> using namespace std; typedef __int64 int64; typedef long long ll; #define M 600005 #define N 1000005 #define max_inf 0x7f7f7f7f #define min_inf 0x80808080 #define mod 1000000007 #define lc rt<<1 #define rc rt<<1|1 int dig[70]; ll dp[70][70][70] , sum[70];//dp[层数][要求幸运数长度][已收到幸运数个数],sum[i]为幸运数长度为i的数的个数 //求幸运数长度为s的数有多少个,tot为当前以有的幸运数个数 ll Dfs(int index , int s , int tot , int lim) { if (tot > s)return 0; if (!index)return s == tot; if (!lim && dp[index][s][tot] != -1)return dp[index][s][tot]; int i , up = lim ? dig[index] : 9; ll ret = 0; for (i = 0 ; i <= up ; i++) { ret += Dfs(index-1 , s , tot+(i==4||i==7) , lim&&i==up); } if (!lim)dp[index][s][tot] = ret; return ret; } //计算其他6个人幸运数小于k的情况数 ll Cal(int index , int k) { if (index >= 6)return 1; int i; ll ret = 0; for (i = 0 ; i < k ; i++) { if (sum[i] > 0) { sum[i]--; //若此人选择幸运数长度为i的数,这后面的人最多能选择的长度为k-i ret += (sum[i]+1)*Cal(index+1 , k-i)%mod; ret %= mod; sum[i]++; } } return ret; } ll Solve(ll k) { int i , len = 0; ll ret = 0; while (k) { dig[++len] = k%10; k /= 10; } //求各长度幸运数的数的个数 for (i = 0 ; i <= len ; i++)sum[i] = Dfs(len , i , 0 , 1); // 0不能选,需要除掉 sum[0]--; //枚举第一个人的幸运数长度 for (i = 1 ; i <= len ; i++) { ret = ret+sum[i]*Cal(0,i)%mod; ret %= mod; } return ret; } int main() { ll m; memset(dp , -1 , sizeof dp); while (~scanf("%I64d",&m)) printf("%I64d\n",Solve(m)); return 0; }

上一篇:影像圣堂PhotoshopCS3八大图像处理技术
下一篇:Android TouchEvent的传递

相关文章

相关评论