定義windy數：相鄰數字的差至少是2的數，例如10不是windy數，而13是windy數。求給定區間中有多少windy數。區間端點范圍為 [1, 2000000000]

dfs寫法 #include <stdio.h> #include <string.h> #define N 10 int dp[N][N],digit[N]; int dfs(int pos,int last,int z,int f) {if(pos==-1) return 1;if(z&&!f&&dp[pos][last]!=-1) return dp[pos][last];int max=f?digit[pos]:9;int ret=0;if(z==0){for(int i=0;i<=max;i++){ret+=dfs(pos-1,i,i,f&&i==max);}}else{for(int i=0;i<=max;i++){if((i-last)*(i-last)<4) continue;ret+=dfs(pos-1,i,1,f&&i==max);}}if(z&&!f) dp[pos][last]=ret;return ret; } int cal(int x) {int pos=0;while(x){digit[pos++]=x%10;x/=10;}return dfs(pos-1,0,0,1); } int main() {memset(dp,-1,sizeof(dp));int a,b;while(~scanf("%d%d",&a,&b)) printf("%d\n",cal(b)-cal(a-1));return 0; } 遞推寫法 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define LEN 15 char a[LEN],b[LEN]; int n,m; int dp[LEN][10][2][2][2]; //第二維記錄最后的數字，第三維記錄狀態是否合法，第四維記錄該位是否是最高位，最后一維記錄是否達到上界 int nextstate(int cur,int last,int in) {if(cur==0 && abs(last-in)>=2) return 0;return 1; } int nextflag1(int cur,int in,int max) {if(cur==1 && in==max) return 1;if(cur==1 && in>max) return -1;return 0; } int nextflag2(int cur,int in) {if(cur==1 && in==0) return 1;return 0; } int DP(char *s,int len) {memset(dp,0,sizeof(dp));dp[0][0][0][1][1]=1;for(int i=1;i<=len;i++)for(int last=9;last>=0;last--)for(int state=0;state<2;state++)for(int flag1=0;flag1<2;flag1++)for(int flag2=0;flag2<2;flag2++)for(int in=0;in<10;in++){int nxt=nextstate(state,last,in);if(flag2==1) nxt=0;if(nextflag1(flag1,in,s[i]-'0')!=-1)dp[i][in][nxt][nextflag1(flag1,in,s[i]-'0')][nextflag2(flag2,in)]+=dp[i-1][last][state][flag1][flag2];}int ret=0;for(int i=0;i<10;i++) ret+=dp[len][i][0][0][0]+dp[len][i][0][1][0];return ret; } int main() {while(~scanf("%d%d",&n,&m)){n--;sprintf(a+1,"%d",n);sprintf(b+1,"%d",m);printf("%d\n",DP(b,strlen(b+1))-DP(a,strlen(a+1)));}return 0; }

轉載于:https://www.cnblogs.com/algorithms/archive/2012/08/02/2620431.html

總結

以上是生活随笔為你收集整理的1026: [SCOI2009]windy数 （按位DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。