Balanced Number HDU - 3709

本文主要是介绍Balanced Number HDU - 3709，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=3709

dp[i][j]代表[i+1,pos-1]的权值和为j时 [0,i]能提供多少解

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=20;
const int maxm=2000;ll dp[maxn][maxm];
int bit[maxn];ll dfs(int pos,int mid,int sta,int limit)
{ll res;int up,i;if(pos==-1) return sta==0;if(sta<0) return 0;if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];if(limit) up=bit[pos];else up=9;res=0;for(i=0;i<=up;i++){res+=dfs(pos-1,mid,sta+i*(pos-mid),limit&&i==bit[pos]);}if(!limit) dp[pos][sta]=res;return res;
}ll solve(ll val)
{ll res;int n,i;if(val==-1) return 0;n=0;while(val>0){bit[n++]=val%10;val/=10;}res=0;for(i=0;i<=n-1;i++){memset(dp,-1,sizeof(dp));res+=dfs(n-1,i,0,1);}return res-(n-1);
}int main()
{ll l,r;int t;scanf("%d",&t);while(t--){scanf("%lld%lld",&l,&r);printf("%lld\n",solve(r)-solve(l-1));}return 0;
}

 

这篇关于Balanced Number HDU - 3709的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---