題目大意: 題目先給出平衡數的概念：數n以數n中的某個位為支點，每個位上的數權值為（數字xi*（posi - 支點的posi）），如果數n裡有一個支點使得所有數權值之和為0那麼她就是平衡數。比如4139，以3為支點，左邊 = 4 * (4 - 2) + 1 * (3 - 2) = 9，右邊 = 9 * (1 - 2) = -9，左邊加右邊為0，所以4139是平衡數。現在給出一個區間[l,r]，問區間內平衡數有多少個？
解題思路：第一道數位DP，之前一直不會做這類題目，今天花了兩個小時看了幾篇博客，略懂皮毛，也參照某神牛的代碼敲了下這題。
這類題目用逆推要比正推好做，方法是記憶化搜索。每次向下傳遞目前的狀態，下面每次都返回通過這些狀態後面能得到的結果。
因為要權值之和為0，我們枚舉每個支點o，然後從高位往地位搜索並記錄狀態，這裡的狀態為當前的位置pos，之前的權值之和pre、支點o，這三個組合起來就可以表示一個狀態。每種狀態都至多遍歷一次，如果第二次遍歷到某個狀態，就直接返回前一次往下遍歷的結果。
上一段已經解釋了Dfs中的三個參數，那還剩下一個參數limit是干什麼的？limit表示是否有上界，如果我們要找的是[0，12345,現在找到123，這時limit還是1，如果下一個枚舉到的數是3，limit就變成0，以後都可以枚舉到9而不是到5.
測試數據：
2
0 9
7604 24324
C艹代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#define MAX 2000
#define int64 long long
int64 dp[20][20][MAX]; //dp記憶化搜索用
int64 digit[20],left,right; //left和right為輸入的一大一小值
int64 Dfs(int64 pos,int o,int64 pre,int limit) {
//pos表示當前位置，o表示支點，pre表示從最高位到pos的力矩之和，limit表示是否有上限 1有 0無
if (pos == -1) return pre == 0; //已經全部組合
if (pre < 0) return 0; //前面組合而成的力矩之和已經小於0，後面的也都是負數
if (!limit && dp[pos][o][pre] != -1)
return dp[pos][o][pre]; //沒有上限且當前的狀態之前已經搜索過
int64 sum = 0;
int64 end = limit ? digit[pos] : 9; //有上限就設為上限，否則最高到9
for (int i = 0; i <= end; ++i) {
int64 next = pre; //枚舉下一個狀態
next += (pos - o) * i;
sum += Dfs(pos-1,o,next,limit && i == end);
}
if (!limit) dp[pos][o][pre] = sum;
return sum;
}
int64 Cal(int64 x) {
int64 pos = 0,ans = 0; //位數,總個數
while (x) {
digit[pos] = x % 10;
x /= 10,pos++;
} www.2cto.com
for (int o = 0; o < pos; ++o) //枚舉支點
ans += Dfs(pos-1,o,0,1);
return ans - pos + 1; //去除全是0的情況
}
int main()
{
int i,j,k,t;
scanf("%d",&t);
while (t--) {
scanf("%lld%lld",&left,&right);
memset(dp,-1,sizeof(dp));
printf("%lld\n",Cal(right) - Cal(left-1));
}
}
