思路：

?

之前想直接開左右兩邊的數(shù)結(jié)果爆內(nèi)存...

枚舉每次pivot的位置，然后數(shù)位DP，如果sum<0返回0，因?yàn)橐呀?jīng)小于零說明已經(jīng)到了pivot右邊，繼續(xù)dfs只會越來越小，且dp數(shù)組會炸

注意一下一些細(xì)節(jié)：dp開long long，注意前導(dǎo)零只能算一次

代碼：

#include<iostream> #include<algorithm> #define ll long long const int N = 50000+5; const int INF = 0x3f3f3f3f; using namespace std; int dig[20]; ll dp[20][20][2000]; ll dfs(int pos,int piv,int sum,bool limit){if(pos == -1) return sum == 0? 1 : 0;if(sum < 0) return 0;if(!limit && dp[pos][piv][sum] != -1) return dp[pos][piv][sum];int top = limit? dig[pos] : 9;ll ret = 0;for(int i = 0;i <= top;i++){int tot;if(pos > piv){tot = sum + (pos - piv)*i;}else if(pos < piv){tot = sum - (piv - pos)*i;}else{tot = sum;}ret += dfs(pos - 1,piv,tot,limit && i == top);}if(!limit) dp[pos][piv][sum] = ret;return ret; } ll solve(ll x){int pos = 0;if(x == -1) return 0;while(x){dig[pos++] = x % 10;x /= 10;}ll ret = 0;for(int i = 0;i < pos;i++){ret += dfs(pos - 1,i,0,true);}return ret - pos + 1; //前導(dǎo)零只能算一次 } int main(){int T;ll l,r;scanf("%d",&T);while(T--){memset(dp,-1,sizeof(dp));scanf("%lld%lld",&l,&r);printf("%lld\n",solve(r) - solve(l - 1));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/KirinSB/p/9408772.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。