1026-windy数+数位DP+记忆化搜索
1026: [SCOI2009]windy数
题意：数位DP模板题；
目前只理解了记忆化搜索，就想练练手，
------给递推写法留一个位子
------
注意这道题要判断前导0的情况，1 ）可以加一个bool lead，或者在（i==0&&pre==-10)特判
#include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cstdio> using namespace std; typedef long long ll; ll dp[10][10],digit[10]; ll dfs(int pos,int pre,bool limit,bool lead)//lead是判断前导0的，如果（i==0&&pre==-10）需要在dfs中继续pre=-10，避免满足记忆化的条件 { if(pos==0)return 1; if(!limit&&dp[pos][pre]>=0&&!lead)return dp[pos][pre]; int num = limit?digit[pos]:9; ll ans = 0; for(int i=0;i<=num;i++) { if(abs(i-pre)<2)continue; if(lead&&i==0) ans += dfs(pos-1,pre,limit&&i==digit[pos],true); else ans+= dfs(pos-1,i,limit&&i==digit[pos],false); } if(!lead && !limit)return dp[pos][pre] = ans; else return ans; } ll solve(ll x) { int len = 0; while(x>0) { digit[++len] = x%10; x/=10; } return dfs(len,-10,true,true); } int main(){ ll n,m; memset(dp,-1,sizeof(dp)); while(~scanf("%lld%lld",&n,&m)) { printf("%lld ",solve(m)-solve(n-1)); } }
贴一张特判的，感觉这个目的性和思路比较清晰；
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; int a, b,num[20],dp[20][12]; int dfs(int len, int last, bool shangxian) { int p; if (len <= 0) return 1; if (!shangxian && dp[len][last] != -1&& last >= 0) return dp[len][last]; int cnt = 0, maxx = (shangxian ? num[len] : 9); for (int i = 0; i <= maxx; i++) { if (abs(i - last) < 2) continue; p = i; if (i == 0 && last == -10) p = last; cnt += dfs(len - 1, p, shangxian && (i == maxx)); } //return cnt; if (last >= 0 && !shangxian) dp[len][last] = cnt; return cnt; } int solve(int x) { int k = 0; while (x) { num[++k] = x % 10; x /= 10; } memset(dp, 255, sizeof(dp)); return dfs(k, -10, true); } int main() { scanf("%d%d", &a, &b); printf("%d ", solve(b) - solve(a - 1)); return 0; }