题目链接:HDU3652

【题意】求1~n之间有多少个数字包含13且能被13整除。

【分析】总算自己能想出数位DP了，我求的是不满足情况的数量，然后答案减一下就好了，用dp[len][mod][is1][ok]表示len位的数字中除以13的余数为mod，上一位是否为1，是否包含13的数字有几个，套下数位DP模版就好了，注意如果包含了13不能不往下递归，可能还有一个条件(mod%13！=0)也需要计数，所以加了一个ok状态看是否包含13，最后在判断不满足条件的数( ((bool)mod) || ok );

【AC CODE】0ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 11;
int dp[MAXN][13][2][2], bit[MAXN];

int dfs(int len, int mod, bool is1, bool ok, bool ismax)//0~n不满足"包含13并且能被13整除"的数量
{
	if(!len) return ((bool)mod) || ok;
	if(!ismax && ~dp[len][mod][is1][ok]) return dp[len][mod][is1][ok];
	int mx = ismax?bit[len]:9, sum = 0;
	repe(i,0,mx)
	{
		if(is1 && 3 == i) sum += dfs(len-1,(mod*10+i)%13,1 == i,0,ismax&&i==mx);
		else sum += dfs(len-1,(mod*10+i)%13,1 == i,ok,ismax&&i==mx);
	}
	return ismax?sum:dp[len][mod][is1][ok] = sum;
}
int sloved(int n)
{
	int len = 0;
	while(n)
	{
		bit[++len] = n%10;
		n /= 10;
	}
	return dfs(len,0,0,1,1);
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	clc(dp,-1);
	while(~scanf("%d", &n))
	{
		printf("%d\n", n-sloved(n)+1);
	}
	return 0;
}

当然是也可以正着来，dp表示符合条件的个数。

【AC CODE】0ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 11;
int dp[MAXN][13][2][2], bit[MAXN];

int dfs(int len, int mod, bool is1, bool ok, bool ismax)
{
    if(!len) return !mod && ok;
    if(!ismax && ~dp[len][mod][is1][ok]) return dp[len][mod][is1][ok];
    int mx = ismax?bit[len]:9, sum = 0;
    repe(i,0,mx)
    {
        if(is1 && 3 == i) sum += dfs(len-1,(mod*10+i)%13,1 == i,1,ismax&&i==mx);
        else sum += dfs(len-1,(mod*10+i)%13,1 == i,ok,ismax&&i==mx);
    }
    return ismax?sum:dp[len][mod][is1][ok] = sum;
}
int sloved(int n)
{
    int len = 0;
    while(n)
    {
        bit[++len] = n%10;
        n /= 10;
    }
    return dfs(len,0,0,0,1);
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int n;
    clc(dp,-1);
    while(~scanf("%d", &n))
    {
        printf("%d\n", sloved(n));
    }
    return 0;
}