首页 > 代码库 > 不要62——数位DP
不要62——数位DP
最近学了数位DP,于是就做了做这道题……
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int getin(){ int num=0,t=1; char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c<=‘9‘&&c>=‘0‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } int main() { freopen("a.in","r",stdin); freopen("2.out","w",stdout); int l,r; while(1){ scanf("%d%d",&l,&r); if(l+r==0)break; int ans=0; for(int i=l;i<=r;i++){ int n=i,t=1; int len=0,digit[10]; while(n!=0){//统计n的位数 digit[++len]=n%10; n/=10; } digit[len+1]=0; for(int j=len;j>=1;j--){ if(digit[j]==4||digit[j]==2&&digit[j+1]==6) t=0; } if(t)ans++; } cout<<ans<<"\n"; } return 0; }
这是一个最普通的做法了,简单的暴力一下。其实也可以打个表。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int dp[15][10]; void init(){//初始化 memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=11;i++){ for(int j=0;j<=9;j++){//枚举第i位可能出现的数 for(int k=0;k<=9;k++){//枚举第i-1位可能出现的数 if(j!=4&&!(j==6&&k==2)) dp[i][j]+=dp[i-1][k]; } } } } int solve(int n){ int digit[15];//从低到高保存n的每一位 int len=0,ans=0; while(n!=0){//统计n的位数 digit[++len]=n%10;n/=10; } digit[len+1]=0;//方便处理 for(int i=len;i>=1;i--){//枚举当前位数 for(int j=0;j<digit[i];j++){ if(j!=4&&!(digit[i+1]==6&&j==2)) ans+=dp[i][j]; } if(digit[i]==4||(digit[i]==2&&digit[i+1]==6)) break; //如果高位出现过“62”或“4”就break } return ans; } int main() { freopen("a.in","r",stdin); freopen("1.out","w",stdout); int l,r; init(); while(1){ scanf("%d%d",&l,&r); if(l+r==0)break; printf("%d\n",solve(r+1)-solve(l)); //因为是solve是计算区间[0,n)的,所以要r+1 } return 0; }
然后现在是正解数位DP了。
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
不要62——数位DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。