洛谷P2657 windy数 [SCOI2009] 数位dp
正解:数位dp
解题报告:
这题一看就是个数位dp鸭,"不含前导零且相邻两个数字之差至少为2"这种的
然后就直接套板子鸭(板子戳总结,懒得放链接辣QAQ
然后就是套路
然后就没了,,,
昂对了这题还有一个,分块暴力做法233333
就很强,很想学
我先把数位dp的代码放上来再港分块暴力方法hhhhh
#include<bits/stdc++.h> using namespace std; #define il inline #define rg register #define ll long long #define rp(i,x,y) for(rg ll i=x;i<=y;++i) #define my(i,x,y) for(rg ll i=x;i>=y;--i) const ll L=12,lq=-20031016; ll a[L],dp[L][10]; il ll read() { rg char ch=getchar();rg ll x=0;rg bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')ch=getchar(),y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } ll dfs(ll pos,ll last,bool limit) { if(!pos)return 1; if(last>0)if(!limit && dp[pos][last]!=-1)return dp[pos][last]; rg ll up=limit?a[pos]:9,as=0,tmp; rp(i,0,up){if(abs(last-i)<2)continue;tmp=i;if((last==lq) && (!tmp))tmp=lq;as+=dfs(pos-1,tmp,limit && tmp==a[pos]);} if(!limit && last>0)dp[pos][last]=as; return as; } il ll solve(ll x) { rg ll pos=0; while(x){a[++pos]=x%10;x/=10;} return dfs(pos,lq,true); } int main() { memset(dp,-1,sizeof(dp));ll x=read(),y=read();printf("%lld\n",solve(y)-solve(x-1)); return 0; }
分块暴力是这样儿的:
首先可以看出,2000000000不是一个很大的数,考虑用暴力
然后为了防止代码过长,可以每隔1000000打出一个数
然后就大块维护局部朴素
妙的是思想,代码很简单,就不放了
主要是懒得打辣QAQ