LightOJ 1032 - Fast Bit Calculations（dp）

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

题目链接：LightOJ 1032 - Fast Bit Calculations

代码

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
const int maxn = 50;ll dp[maxn + 5][maxn + 5][2];int main () {int cas;scanf("%d", &cas);for (int kcas = 1; kcas <= cas; kcas++) {int n, bit[maxn + 5];scanf("%d", &n);for (int i = maxn; i >= 0; i--) {bit[i] = (n&1);n >>= 1;}int p = 0;memset(dp, 0, sizeof(dp));for (int i = 1; i <= maxn; i++) {for (int k = 0; k < maxn; k++) {for (int x = 0; x < 2; x++)for (int y = 0; y < 2; y++) {int v = k + (x&y);dp[i][v][y] += dp[i-1][k][x];}}for (int j = 0; j < bit[i]; j++)dp[i][p][j]++;if (bit[i-1] && bit[i]) p++;}ll ret = p;for (int i = 0; i < maxn; i++)ret += (dp[maxn][i][0] + dp[maxn][i][1]) * i;printf("Case %d: %lld\n", kcas, ret);}return 0;
}

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

---