BZOJ 1799 [Ahoi2009]self 同类分布 数位DP

本文主要是介绍BZOJ 1799 [Ahoi2009]self 同类分布 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1799: [Ahoi2009]self 同类分布

Time Limit: 50 Sec   Memory Limit: 64 MB
Submit: 1211   Solved: 517
[ Submit][ Status][ Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

Source

穷举数位和

DP记录三个量：长度，数位和，当前数字除以数位和的余数。

至于剩下的，套一套模板。

不过这个DP的状态挺难想的。

#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <bitset>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f; 
ll dp[20][165][165];
int num[20];ll dfs(int len,int sum,int mod,int nu,bool HaveLimit) {if (sum>len*9) return 0;if (len==0) return sum==0&&nu==0;if (dp[len][sum][nu]!=-1&&!HaveLimit) return dp[len][sum][nu];int p=HaveLimit?num[len]:9;ll ans=0;for (int i=0;i<=p;i++) {ans+=dfs(len-1,sum-i,mod,(nu*10+i)%mod,HaveLimit&&i==num[len]);}if (!HaveLimit) dp[len][sum][nu]=ans;return ans;
}ll solve(ll n) {int len=0,i;ll k=n;while (k) {num[++len]=k%10;k/=10;}ll ans=0;for (i=1;i<=9*len;i++) {memset(dp,-1,sizeof(dp));ans+=dfs(len,i,i,0,1);}return ans;
}int main() {ll a,b;while (scanf("%lld%lld",&a,&b)!=EOF) {ll ans=solve(b)-solve(a-1);printf("%lld\n",ans);}return 0;
}

这篇关于BZOJ 1799 [Ahoi2009]self 同类分布 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---