首页 > 代码库 > 几道数位dp
几道数位dp
hdu2089 不要62
/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int> vi;int n,m;int dp[10][3];int bit[10];void ini(){ mset(dp); dp[0][1]=1; for(int i=1; i<=6; i++){ dp[i][0] = dp[i-1][1]; dp[i][1] = dp[i-1][1]*9 - dp[i-1][0]; dp[i][2] = dp[i-1][2]*10 + dp[i-1][1] + dp[i-1][0]; }}int solve(int x){ int ans=0,len=0,tmp=x; bool flag=0; mset(bit); while(x){ bit[++len] = x%10; x/=10; } bit[len+1]=0; //为了bit[i+1]=6 && bit[i]>2这一步 for(int i=len;i;i--){//前i位数,第i位不为0,不吉利数为ans ans += dp[i-1][2]*bit[i]; if(flag){ ans+=dp[i-1][1]*bit[i]; continue; } if(bit[i]>4) ans+=dp[i-1][1]; if(bit[i+1]==6 && bit[i]>2) ans+=dp[i][0]; if(bit[i]>6) ans+=dp[i-1][0]; if((bit[i+1]==6 && bit[i]==2) || bit[i]==4) flag=1; } return tmp-ans;}int main(){// freopen("a.txt","r",stdin);// freopen(".out","w",stdout); ini(); while(cin>>n>>m,n|m){ cout<<solve(m+1)-solve(n)<<endl; } return 0;}/*DESCRIPTION:先做预处理前i位数,不存在不吉利号码,最高位是2 dp[i][0].......,不存在不吉利号码,最高位包括2 dp[i][1].......,存在不吉利号码 dp[i][2]dp[i][0] = dp[i-1][1];dp[i][1] = (dp[i-1][1]-dp[i-1][0])*9 + dp[i-1][0]*8 = dp[i-1][1]*9 - dp[i-1][0] //最高位可以是0dp[i][2] = dp[i-1][2]*10 + dp[i-1][0]*2 + (dp[i-1][1]-dp[i-1][0]) = dp[i-1][2]*10 + dp[i-1][0] + dp[i-1][1] dp[1][0] = 1;dp[1][1] = 9;dp[1][2] = 1;利用solve(n)计算小于n的吉利号码的个数ans = solve(m+1) - solve(n);*/
hdu3555 bomb
/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int> vi;int t;ll n;ll dp[20][3];int bit[20];void ini(){ mset(dp); dp[0][1]=1; rep(i,1,16){ dp[i][0]=dp[i-1][1]; dp[i][1]=10*dp[i-1][1] - dp[i-1][0]; dp[i][2]=dp[i-1][0] + dp[i-1][2]*10; }}ll solve(ll x){ int len=0; while(x){ bit[++len] = x%10; x/=10; } ll ans=0; bool flag=0; bit[len+1]=0; for(int i=len;i;i--){ ans+=dp[i-1][2]*bit[i]; if(flag){ ans+=dp[i-1][1]*bit[i]; continue; } if(bit[i]>4) ans+=dp[i-1][0]; if(bit[i+1]==4 && bit[i]==9) flag=1; } return ans;}int main(){// freopen("a.txt","r",stdin);// freopen(".out","w",stdout); cin>>t; ini(); while(t--){ cin>>n; cout<<solve(n+1)<<endl; } return 0;}/*DESCRIPTION:最高在16位前i位,最高位为9,不存在49,dp[i][0].....,不存在49,dp[i][1].....,存在49,dp[i][2]dp[1][0]=1dp[1][1]=10dp[1][2]=0dp[i][0]=dp[i-1][1]dp[i][1]=(dp[i-1][1]-dp[i-1][0])*10 + dp[i-1][0]*9 = 10*dp[i-1][1] - dp[i-1][0]dp[i][2]=dp[i-1][0] + dp[i-1][2]*10*/
hdu3652 dfs写法 含有13且是13的倍数
/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int> vi;int n;int bit[11];int dp[12][12][3];int dfs(int pos, int mod, int status, bool limit){ if(pos<=0) return status==2 && mod==0; //含有13,且是13的倍数 if(!limit && dp[pos][mod][status]!=-1) return dp[pos][mod][status];// 判重 int end=limit?bit[pos]:9, ans=0; for(int i=0;i<=end;i++){ int nstatus = status; int nmod = (mod*10+i)%13; if(status==0 && i==1) nstatus = 1; else if(status==1 && i==3) nstatus = 2; else if(status==1 && i!=1) nstatus = 0; ans+=dfs(pos-1, nmod, nstatus, limit && i==end); } if(!limit) dp[pos][mod][status] = ans; return ans;}/*6 3 1 3 0 pos对于pos这一位,如果前面一位已经到了6(limit),当前pos这位就只能到3,如果前面一位小于6,当前这位就!limitstatus=0 不含13, 末位不是1status=1 不含13, 末位是1status=2 含13其实dfs的写法比递推的写法更具有灵活性,而且不容易写错当!limit时,pos位之后的dp[pos][mod][status]已经被求出,则把这个值保存下来,防止重复计算*/int solve(int x){ mset(bit); int len=0; while(x){ bit[++len] = x%10; x/=10; } memset(dp,-1,sizeof(dp)); return dfs(len, 0, 0, 1);}int main(){ freopen("a.txt","r",stdin);// freopen(".out","w",stdout); while(cin>>n){ cout<<solve(n+1)<<endl; } return 0;}/*DESCRIPTION:余数为j不存在13,以3为最高位 dp[i][j][0]不存在13 dp[i][j][1]存在13 dp[i][j][2]dp[i][ (dp[i-1][j][1]+3*md[i-1])%13 ][0] += dp[i-1][j][1]dp[i][ (dp[i-1][j][0]+k*md[i-1])%13 ][1] += dp[i-1][j][1] k=0,1,...9dp[i][ (dp[i-1][j][0]+k*md[i-1])%13 ][1] -= dp[i-1][j][0]dp[i][ (dp[i-1][j][0]+md[i-1])%13 ][2] += dp[i-1][j][0]dp[i][ (dp[i-1][j][2]+k*md[i-1])%13 ][2] += dp[i-1][j][2] k=0,1...9*/
几道数位dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。