HDU 3652 数位DP

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

题目链接
题意：1 - n中有多少个数能被13整除而且包含【13】

数位dp

状态dp[i][j][k][f]
第i位为j 除以13的余数为k
f两个状态
0：没有包含13的个数
1：包含13的个数

状态转移方程：
f = 1，j ！= 1 ： dp[i][j][k][f] = SUM{ dp[i - 1][p][ (k - (j * 10 ^ (i - 1) ) + 13 ) % 13][1] ( p = 0 ～ 9）

f = 1，j = 1 : dp[i][j][k][f] = SUM{ dp[i - 1][p][ (k - (j * 10 ^ (i - 1) ) + 13 ) % 13][1] ( p = 0 ～ 9） + dp[i - 1][3][ (k - (j * 10 ^ (i - 1) ) + 13 ) % 13][0]

f = 0 ,j = 1 dp[i][j][k][f] = SUM{ dp[i - 1][p][ (k - (j * 10 ^ (i - 1) ) + 13 ) % 13][0] ( p = 0 ～ 9） - dp[i - 1][3][ (k - (j * 10 ^ (i - 1) ) + 13 ) % 13][0]

f = 0,j != 1 dp[i][j][k][f] = SUM{ dp[i - 1][p][ (k - (j * 10 ^ (i - 1) ) + 13 ) % 13][0] ( p = 0 ～ 9）

构造解：
构造解时形如一下的数： ####%××××
（#）为已经确定的数
（%）为当前枚举的数
（X）为待枚举的数

设pre_mode 为 ####00000 除以13的余数

为了构造出能被13整除的数所有后部分对13取模应为 w =（13 - pre_mode) % 13
has_13 表示已确定的数中是否已经包含了13

has_13 = 0 此时我们要构造出有包含了13 且和已确定的数组合在一起能被13整除的数 dp(i,j,w,1) 如果此时num[i + 1] = 1 且num[i] > 3 时我们可以从一个不含13的数的前面加上以确定部分形成正确解 dp[i][3][w][0]

has_13 = 1 此时我们只要在未确定部分构造出能被一个和确定部分组合后能被13整除的数即可 SUM{ dp[i][p][w][0] + dp[i][p][w][1] } p = 0 ～ 9

最后：作为一个菜鸡，1A了很开心

代码如下：

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define sf scanf
#define pf printf
using namespace std;
int dp[15][10][13][2];
int LARGE[10];
int digit[15];
void init(){LARGE[1] = 1;for(int i = 2;i < 10;++i){LARGE[i] = LARGE[i - 1] * 10;LARGE[i] %= 13;}memset(dp,-1,sizeof(dp));memset(dp[0],0,sizeof(dp[0]));memset(dp[1],0,sizeof(dp[1]));for(int j = 0;j < 10;++j){dp[1][j][j % 13][0] = 1;}
}int DPS(int i,int j,int k,bool f){          //第i位为j mod 13 为 k  有/没 包含13int& ans = dp[i][j][k][f];if(ans != -1) return ans;ans = 0;if(f){int w = (k - (j * LARGE[i]) % 13 + 13) % 13;for(int p = 0;p < 10;++p){ans += DPS(i - 1,p,w,1);}if(j == 1){ans += DPS(i - 1,3,w,0);}}else{int w = (k - (j * LARGE[i]) % 13 + 13) % 13;for(int p = 0;p < 10;++p){ans += DPS(i - 1,p,w,0);}if(j == 1){ans -= DPS(i - 1,3,w,0);}}return ans;
}int get_digit(int n){for(int i = 1;n;++i){digit[i] = n % 10;n = n / 10;if(!n) return i;}
}int main(){init();int n;while( ~sf("%d",&n) ){int ans = 0,len = get_digit(n);digit[len + 1] = 0;int pre_mod = 0;bool has_13 = false;for(int i = len;i;--i){for(int j = 0;j < digit[i];++j){if(has_13){ans += DPS(i,j,(13 - pre_mod) % 13,1);ans += DPS(i,j,(13 - pre_mod) % 13,0);}else{ans += DPS(i,j,(13 - pre_mod) % 13,1);}}if(!has_13 && digit[i + 1] == 1 && digit[i] > 3){ans += DPS(i,3,(13 - pre_mod) % 13,0);}pre_mod = (pre_mod + digit[i] * LARGE[i] ) % 13;if(digit[i + 1] == 1 && digit[i] == 3) has_13 = 1;}if(has_13 && n % 13 == 0) ans++;pf("%d\n",ans);}return 0;
}

DFS版本：

代码:

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define sf scanf
#define pf printf
using namespace std;
typedef long long LL;int dp[13][3][13];  //dp[i][st][prev] 第i位 前缀数字 模13为prev st      //3种状态 //0 前面没有13 i + 1位不是1  //1 前面没有13 i + 1位是1//2 前面有13
int digit[13];
int dfs(int i,int st,int prev,bool flag){if(i == 0) return !flag && st == 2 && prev == 0;if(!flag && ~dp[i][st][prev]) return dp[i][st][prev];int limit = flag ? digit[i] : 9;int ans = 0;for(int j = 0;j <= limit;++j){int nst;if(st == 0){if(j == 1){nst = 1;}else nst = 0;}else if(st == 1){if(j == 1){nst = 1;}else if(j == 3){nst = 2;}else nst = 0;}else nst = 2;ans += dfs(i - 1,nst,(prev * 10 + j) % 13,flag && j == limit);}if(!flag) dp[i][st][prev] = ans;return ans;
}int solve(int n){int len = 0;while(n) digit[++len] = n % 10,n = n / 10;return dfs(len,0,0,1);
}int main(){memset(dp,-1,sizeof(dp));int n;while(~sf("%d",&n)) pf("%d\n",solve(n + 1));return 0;
}