lightoj 1032 - Fast Bit Calculations （数位DP）

本文主要是介绍lightoj 1032 - Fast Bit Calculations （数位DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

记忆花搜索：dp[len][num][last] : 现在处理第len位，前面有num个11，并且最后一位为last。

/************************************************ Author: fisty* Created Time: 2015-08-18 20:18:09* File Name   : 1032.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
#define MAX_N 32
int t;
int digit[MAX_N];
LL dp[MAX_N][MAX_N][2];
LL dfs(int len, int num, int e, int last){//当前在第len位， 前面有num个11，边界信息为e，最后一位为lastif(len < 0) return num;if(!e && dp[len][num][last] != -1) return dp[len][num][last];LL ans = 0;int end = (e ? digit[len] : 1);for(int i = 0; i <= end; i++){if(i && last){//上一位和此位都为1ans += dfs(len-1, num+1, e&&i==end, i);}else{ans += dfs(len-1, num, e&&i==end, i);}}if(!e) dp[len][num][last] = ans;return ans;
}
LL solve(int n){int len = 0;Memset(dp, -1);while(n){digit[len++] = n % 2;n /= 2;}return dfs(len-1, 0, 1, 0);
}
int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);scanf("%d", &t);int cnt = 1;while(t--){int n;scanf("%d", &n);printf("Case %d: %lld\n", cnt++, solve(n));}return 0;
}

这篇关于lightoj 1032 - Fast Bit Calculations （数位DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---