題目鏈接：點擊查看

題目大意：將一串數字視為天平，兩端平衡的數字稱為平衡數，并求出一段閉區間中平衡數的個數。所謂的平衡條件即為力臂與

力相乘后兩端的數量和可以抵消，例如數字4139可以視為以3為中軸的天平，天平左邊：4*2+3*1=9，天平右邊：9*1=9。

題目分析：數位dp，輸入一個數后對其每一位進行枚舉測試，即令該位置當中軸時，統計滿足條件的個數，最后再減去(len-1)即

可，因為0被多算了len-1次。

這個題中令dp[len][pos][sum]，len指的是每一位，pos指的是當前當做中軸的位置，sum指的是從最高位深搜到最后一個位置中

力臂與力乘積的總和，即中軸左側的sum總是遞增，sum在右側總是遞減，可以利用這個性質剪枝，即sum<0時可以直接返回0

了，因為已經不可能達到平衡了。

注意在開數組的時候，因為范圍內的數字最大只有18位，所以假設每次都是極端情況，即每位上的數字最大，例如9999....

這樣力臂與力的乘積變成了9*（18-1）+9*（18-2）.....9*1<=9*18*18=2916<=3000，所以sum的數組開到3000就已經穩夠了

上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=800;int k;LL dp[25][25][3000];int b[25];LL dfs(int len,int pos,int sum,bool limit) {if(len==-1)return sum==0;if(sum<0)return 0;if(!limit&&dp[len][pos][sum]!=-1)return dp[len][pos][sum];int up=limit?b[len]:9;LL ans=0;for(int i=0;i<=up;i++){ans+=dfs(len-1,pos,sum+(len-pos)*i,limit&&i==b[len]);}if(!limit)dp[len][pos][sum]=ans;return ans; }LL solve(LL n) {int cnt=0;while(n){b[cnt++]=n%10;n/=10;}LL ans=0;for(int i=0;i<cnt;i++){ans+=dfs(cnt-1,i,0,true);}return ans-cnt+1; }int main() { // freopen("input.txt","r",stdin);memset(dp,-1,sizeof(dp));int w;cin>>w;while(w--){LL a,b;cin>>a>>b;cout<<solve(b)-solve(a-1)<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 3709 Balanced Number(数位dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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