?
问0~N内所有数的二进制形式中出现的连续的'11'的个数的和。
与LightOJ 1140类似，都是对一个数内一些特征的数目计数，像一个数中'11'或'0'的个数和。
设dp[i][j]表示处理到第i位时'11'出现的次数。
NC的错误，数组开小了，还一直觉得是十进制。。。
#include #include #include #include #include #include #include #include #include #include #include #include #include //#define LL __int64 #define LL long long #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; int dig[40]; LL dp[40][3][40]; //dp[i][j]表示到第i位有j个(1,1)对 LL dfs(int len, int pre, int sta,int up,int first) { if(len == 0) { if(first) return 0; return (LL)sta; } if(!up && !first && dp[len][pre][sta] != -1) return dp[len][pre][sta]; int n = up ? dig[len] : 1; LL res = 0; for(int i = 0; i <= n; i++) { if(first) res += dfs(len-1,i,0,up&&i==n,first&&i==0); else { if(i == 1 && pre == 1) res += dfs(len-1,i,sta+1,up&&i==n,first&&i==0); else res += dfs(len-1,i,sta,up&&i==n,first&&i==0); } } if(!up && !first) dp[len][pre][sta] = res; return res; } LL cal(int num) { int len = 0; while(num) { dig[++len] = num % 2; num /= 2; } return dfs(len,0,0,1,1); } int main() { int num; int test; scanf(%d,&test); for(int item = 1; item <= test; item++) { memset(dp,-1,sizeof(dp)); scanf(%d,&num); printf(Case %d: %lld ,item,cal(num)); } return 0; }