http://acm.timus.ru/problem.aspx?space=1&num=1057

其實這題可以算是一個組合數的題目了，主要是將基于其他進制轉化為基于2進制的算法，對于某一位不為1的話，那么取其他位的話是一定不滿足題意的，所以要找到一個數的最高位大于1，將這一位以及后面的每一位都賦值為1，然后就是一個按位DP的過程了，dp[len][statu]表示長度剩余量為len，要求1的個數為statu個時，并且對后面的位沒有要求的情況下，所有可能的解。

代碼如下：

#include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std;typedef unsigned int Int;Int x, y, k, b, bit[35];int len, dp[35][35];Int dfs(int pos, int statu, int limit) { if (pos == -1) {return statu == 0;}if (!limit && dp[pos][statu] != -1) return dp[pos][statu];Int sum = 0;int s, end = limit ? bit[pos] : 1;for (int i = 0; i <= end; ++i) {s = statu;if (i == 1) s = statu - 1;if (s < 0) continue;sum += dfs(pos-1, s, limit && i==end);}if (!limit) {dp[pos][statu] = sum; // 如果有限制的話，那么end的取值是并沒有取全的 }return sum; }Int Cal(Int x) {len = -1;while (x != 0) { bit[++len] = x % b;x /= b;}if (b != 2) {// 對于不是2進制的數，我們需要將其轉化為2進制進行求解// 若一個數被表示為 a1*b^e1 + a2*b^e2 + a3*b^e3 次方，那么這個數要能成為題目中要求的數// 就要在把這個數縮小的情況下不對解帶來影響，所以我們選擇從高位開始的第一個系數既// 不是0又不是1的位來進行處理，并把從這一位開始的后面的所有的位都變成1，這樣就是舍棄了// 一部分一定不會成為解的數，但是有會所有解空間for (int i = len; i >= 0; --i) {if (bit[i] > 1) {for (int j = i; j >= 0; --j) {bit[j] = 1;}break;}}}return dfs(len, k, 1); }int main() { memset(dp, 0xff, sizeof (dp));while (scanf("%u %u %u %u", &x, &y, &k, &b) == 4) {x -= 1; printf("%u\n", Cal(y) - Cal(x));}return 0; }

轉載于:https://www.cnblogs.com/Lyush/archive/2012/08/13/2636552.html

總結

以上是生活随笔為你收集整理的timus-1507 Amount of Degrees 按位DP的全部內容，希望文章能夠幫你解決所遇到的問題。

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