罗湖网站建设报价,tk网站注册,网页设计时尚页面,wordpress商城模板下载题意
在l到r区间内求有多少个符合条件“当前数中所有连续的奇数长度是偶数 所有连续的偶数长度是奇数”的个数分析
典型的数位dp问题
我们设置dp数组时可以根据 dp[pos][pre][len]设定
表示在pos长度下 前面是pre并且长度是len的个数共有多少这个方法很巧妙
根据这个结构 我…题意
在l到r区间内求有多少个符合条件“当前数中所有连续的奇数长度是偶数 所有连续的偶数长度是奇数”的个数分析
典型的数位dp问题
我们设置dp数组时可以根据 dp[pos][pre][len]设定
表示在pos长度下 前面是pre并且长度是len的个数共有多少这个方法很巧妙
根据这个结构 我们dfsposprelenzerolimit这样设置递归参数
我们把所有可能符合条件的分支都去搜索一遍
当我们到pos0的时候 判断一下 此时如果pre和len的奇偶性不同 那么就返回1 表示这个数字
符合条件
因为当我们递归的时候是把所有可能的尝试都去做了一遍 所以如果当下的数 可能产生正确结果
就根据我们设置的dfs结构递归下去 最终都依靠 pos0的判断 和之前所做的备忘得到结果
和缩小时间复杂度code
#includebits/stdc.h
using namespace std;
typedef long long ll;
int d[20];//1 2 3 4 5 6 7 8 9 10
ll dp[20][20][20];
ll dfs(int pos,int pre,int len,bool zero,bool lim){if(pos0)return (pre1)!(len1);if(!lim~dp[pos][pre][len])return dp[pos][pre][len];ll ans0;int up lim0?9:d[pos];for(int i0;iup;i){//为了计算得到正确结果 我们尝试把所有可能产生计数的可能都走一遍if(zero){//如果存在前导0 那么可能产生计数的情况是 当前位0或!0 都要搜索一遍if(i0)ansdfs(pos-1,0,0,1,iuplim);//当前位为0 那么继续加一位前导0继续搜索else ansdfs(pos-1,i,len1,0,iuplim);//非0 zero0继续搜索 }else{if(i1){//如果是奇数if(pre1)ansdfs(pos-1,i,len1,0,iuplim);//继续搜索else if(len1)ansdfs(pos-1,i,1,0,iuplim);//如果是偶数 长度是也是奇数 那么改变奇偶性 长度为1 继续搜}else{if(!(pre1))ansdfs(pos-1,i,len1,0,iuplim);//如果上一位偶数 那么长度递增 继续搜else if(!(len1))ansdfs(pos-1,i,1,0,iuplim);//如果上一位是奇数 长度变1继续搜 }}}if(!lim)dp[pos][pre][len]ans;return ans;
}
ll solve(ll x){int j0;while(x){d[j] x%10;x/10;}return dfs(j,0,0,1,1);
}
int main()
{int t;ll l,r;scanf(%d,t);for(int i1;it;i){scanf(%lld%lld,l,r);printf(Case #%d: ,i);memset(dp,-1,sizeof(dp));printf(%lld\n,solve(r)-solve(l-1));}return 0;
}
