Balanced Number HDU - 3709 数位dp
题意: 给出范围 算出 满足 选取一个数中任一一个 树作为支点 两边的数分别乘以到中心的距离和 左和等于右和 的数有多少个
数位DP题 状态转移方程为dp[pos][x][state]=dp[pos-1][x][state-(pos-x)*i] 表示为pos位上的数字为 i 以x为支点 则 以中心点左为负右为正 pos左右的数乘以权值的 和为state pos-1位就是 把pos位的 i乘以权值减去 即 state-(pos-x)*i 如果枚举到最后一位的时候 state==0就说明平衡了 其中 0 00 000 000 ......也是平衡的 出了0其他都是非法的要减去
#include <cstdio> #include <cmath> #include <algorithm> #include<vector> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const int MOD=2520; int cnt; ll a[100]; int t[300]; ll dp[20][20][3000]; ll dfs(int pos,int x,int state,bool limit ){ if(pos==-1)return !state; if(!limit&&dp[pos][x][state]!=-1)return dp[pos][x][state]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++){ ans+=dfs(pos-1,x,state+i*(pos-x),limit&&up==i); } if(!limit) dp[pos][x][state]=ans; return ans; } ll solve(ll x){ int pos=0; while(x){ a[pos++]=x%10; x/=10; } ll ans=0; for(int i=0;i<pos;i++)ans+=dfs(pos-1,i,0,1); return ans-pos+1;// 减去00 000 000 其中单0算 所以加一 } int main() { ll a,b; int t; cin>>t; memset(dp,-1,sizeof(dp)); while(t--){ cin>>a>>b; printf("%I64d\n",solve(b)-solve(a-1)); } return 0; }
