HDU 5898 （数位DP）

数位DP）"/>

HDU 5898 （数位DP）

HDU 5898 odd-even number

题意：如果一个数连续的奇数之和为偶数，连续的偶数之和为奇数则满足条件，问某一区间内满足条件的数字的个数。

思路：数位DP，dp[i][j][k][u]表示计算到底i位，是否为临界值，上一位是奇还是偶，连续奇或偶有u个，在dfs是多记录一下该数前面是不是全为0以及该数是不是已近不满足条件。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
vector<int> v;
LL l,r;
LL dp[25][2][2][25];//第i位,是否为临界值,上一位是奇还是偶,连续或偶的个数
LL dfs(int pos,int pan,int status,int num,int ok1,int ok2){if(ok1) return 0;if(pos<0){if(ok2==0) return 0;if(status==1&&num%2==0)return 1;if(status==0&&num%2==1)return 1;return 0;}if(dp[pos][pan][status][num]!=-1)return dp[pos][pan][status][num];LL cnt=0;int k=pan?v[pos]:9;for(int i=0;i<=k;i++){int nowpan,nowstatus,nownum;int nowok1=0,nowok2=0;nowpan=(pan&&(i==k))?1:0;if(i==0){//该位为0if(ok2==0){//前面全是0nowok2=0;nownum=0;nowstatus=0;}else{//前面并非全是0nowok2=1;nowstatus=0;if(status==1){//前一个是奇,这个发生改变nownum=1;if(num%2==1)nowok1=1;}else{//前一个是偶,这个继续nownum=num+1;}}}else if(i%2==1){//非0且为奇nowok2=1;nowstatus=1;if(status==1){//前面为奇,继续nownum=num+1;}else{//前面为偶,发生改变nownum=1;if(num%2==0&&num!=0)nowok1=1;}}else{//非0且为偶nowok2=1;nowstatus=0;if(status==1){//前面为奇,发生改变nownum=1;if(num%2==1&&num!=0)nowok1=1;}else{//前面为偶,继续nownum=num+1;}}//printf("%d %d %d %d %d\n",nowpan,nowstatus,nownum,nowok1,nowok2);cnt+=dfs(pos-1,nowpan,nowstatus,nownum,nowok1,nowok2);}return dp[pos][pan][status][num]=cnt;
}
int main(){int t; cin>>t;int T=t;while(t--){cin>>l>>r;l--;v.clear();memset(dp,-1,sizeof(dp));while(l){v.push_back(l%10);l/=10;}int len=v.size()-1;LL a=dfs(len,1,1,0,0,0);v.clear();memset(dp,-1,sizeof(dp));while(r){v.push_back(r%10);r/=10;}len=v.size()-1;LL b=dfs(len,1,1,0,0,0);printf("Case #%d: ",T-t);cout<<b-a<<endl;}return 0;
}

转载于:.html