那个网站做拍手比较好,网站建设ppt方案模板,濮阳机械设备企业网站建设,dede网站婚纱模板[SCOI2009] windy数 题目大意:求\([L,R]\)中相邻每一位之差至少大于\(2\)的数字个数,(只有一位也算) Solution 数位\(dp\)直接搞,对于前导零,其实不用卡下界,只要一个用一个状态来表示就好,还可以取\(0\) Code #include iostream
#include cstdio
#include iostream
#include cstdio
#include algorithm
#include cstring
#include cstdlib
#define pf(x) printf(%d\n, x);int dp[15][15];
int a[15];int dfs(int pos, int last, bool uflag, bool dflag){if(pos 0 last 0) return 1;else if(pos 0) return 0;//全是0 if(!uflag !dflag dp[pos][last] ! -1) return dp[pos][last];//不用卡上下界,是一个完全状态 int up uflag ? a[pos] : 9;//取上界 int tmp 0;//不用取下界,因为可以为0 for(int i 0; i up; i){if(abs(i - last) 2 || last -233){if(i 0 dflag)//依然为0 tmp dfs(pos - 1, -233, uflag (i up), (i 0) dflag );else //随便了 tmp dfs(pos - 1, i, uflag (i up), 0);}}if(!uflag !dflag) dp[pos][last] tmp;//完全状态 return tmp;
}inline int cal(int x){int cnt -1; memset(a, 0, sizeof(a));while(x){a[cnt] x % 10;x / 10;}int qwq dfs(cnt, -233, 1, 1);return qwq;
}int main(){int l, r;scanf(%d %d, l, r);memset(dp, -1, sizeof(dp));//0printf(%d, cal(r) - cal(l - 1));return 0;
}转载于:https://www.cnblogs.com/LMSH7/p/9621300.html
