HDU 3709 Balanced Number (數位DP)

題意

求出[x, y] 范圍內的平衡數，平衡數定義為：以數中某個位為軸心，兩邊的數的偏移量為矩，數位權重，使得整個數平衡。

思路

外層枚舉平衡點，然后數位DP即可。設計狀態： dp[pos][o][left_right] 表示處理到當前pos位，一開始枚舉o點為支點，前pos-1位左邊減右邊的權值是left_right的數的個數。 注意：1.減法可能為負，所以需要加一個位移偏量，這里我設為2000；2.對于一個正數，如果它是 Balanced Number，那么它有且只有一個平衡點。但是計算0時枚舉所有的支點都會把他算在內一次，重復計算了(位數-1)次。所以最后結果要減去。 PS:外層枚舉支點要比內層枚舉支點剪枝效果更好。

代碼

? [cpp] #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <set> #include <stack> #include <queue> #define MID(x,y) ((x+y)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, m) for (int i = begin; i < begin+m; i ++) using namespace std; typedef long long LL; typedef vector <int> VI; typedef set <int> SETI; typedef queue <int> QI; typedef stack <int> SI; const int oo = 0x7fffffff; VI num; LL dp[20][20][4000]; LL dfs(int pos, int o, int left_right, bool limit){ if (pos == -1) return (left_right == 2000); if (!limit && ~dp[pos][o][left_right]) return dp[pos][o][left_right]; int end = limit?num[pos] : 9; LL res = 0; for (int i = 0; i <= end; i ++){ res += dfs(pos-1, o, left_right+i*(o-pos), limit && (i==end)); } if (!limit) dp[pos][o][left_right] = res; return res; } LL cal(LL x){ if (x < 0) return 0; num.clear(); while(x){ num.push_back(x%10); x /= 10; } MEM(dp, -1); LL ans = 0; for (int i = 0; i < (int)num.size(); i ++){ ans += dfs(num.size()-1, i, 2000, 1); } return ans - num.size() + 1; } int main(){ //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); int t; scanf("%d", &t); while(t --){ LL x, y; scanf("%I64d %I64d", &x, &y); printf("%I64d\n", cal(y) - cal(x-1)); } return 0; } [/cpp]