HDU3652

#include <bits/stdc++.h>

using namespace std;

int digit[12];
int dp[12][13][3];


int DFS(int pos, int pre, int have, int flag)
{
    if(pos == -1) return have == 2 && pre == 0;
    if(!flag && dp[pos][pre][have] != -1) return dp[pos][pre][have];
    int end = flag ? digit[pos] : 9;
    int ans = 0;
    int tmp;
    for(int i=0; i<=end; i++)
    {
        int nhave = have;
        if(have == 1)
        {
            if(i == 3)
            nhave = 2;
            else if( i != 1) nhave = 0;
        }
        if(have != 2 && i == 1) nhave = 1;
        tmp = (pre * 10 + i) % 13;
        ans += DFS(pos-1, tmp, nhave, i==end && flag);
    }
    if(!flag)
        dp[pos][pre][have] = ans;
    return ans;
}

int Cal(int n)
{
    int pos = 0;
    while(n)
    {
        digit[pos++] = n % 10;
        n /= 10;
    }
    return DFS(pos - 1, 0, 0, 1);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n;
    while(~scanf("%d", &n))
    {
        memset(dp, -1, sizeof(dp));
        cout<<Cal(n)<<endl;
    }
    return 0;
}

HDU3652

原文：http://blog.csdn.net/dojintian/article/details/44652395