UVALive 3782 Bigger is Better（数位DP + 大数）

题目大意：每个数字可以分别由几根火柴棒拼起来，给你火柴棒的总数 n ，和 m ，问你用n个火柴棒去拼出来的最大的能被m整除的数是多少？

思路：很裸的数位DP，只是其中有个大数处理，这也是比较麻烦的地方。。。= = ?设 d[ i ][ j ] 表示用 i 根火柴棒去拼，当前已有的余数为 j 的最大整数，则d[ i ][ j ] = max( d[ i - size[ num ] ][ ( j*10 + num)%m ] )，num 为 数字0~9，size 为 该 num 所需的火柴棒数。由于是大数，再开以为表示数字，然后再标记一下长度，也可以搞个结构体清楚一点。

这道题是自己敲得，因为感觉思路比较明确，由于只用到了*10+num的运算和比较，就直接手敲大数了，不过WA了好几发，原因是我 tmp 先开始是全局变量，在递归树里，它会在其他节点里发生变化，开在节点里就过了。。

代码如下；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int size[]={6,2,5,4,6,3,7,6};

int m;

char d[101][3003][51];

int len[101][3003];

bool vis[101][3003];

void dfs(int n,int k,int level)
{
    //printf("n = %d,k = %dn",n,k);
    if(vis[n][k]) return ;
    vis[n][k] = 1;
    int tmp[55];
    int tmp_len = -1;
    if(level > 0 && k == 0)
    {
        tmp_len = 0;
    }
    for(int i = 0;i<=9;i++)
    {
        int to_n = n - size[i];
        int to_k = (k*10 + i)%m;
        if(to_n < 0) continue;
        //printf("i = %d,sz = %dn",i,size[i]);
        dfs(to_n,to_k,level + 1);
        if(len[to_n][to_k] == -1) continue;
        if(tmp_len == -1 || len[to_n][to_k] + 1 > tmp_len)
        {
            tmp_len = len[to_n][to_k] + 1;
            tmp[tmp_len-1] = i;
            for(int j = 0;j<len[to_n][to_k];j++)
                tmp[j] = d[to_n][to_k][j];
        }
        else if(len[to_n][to_k] + 1 == tmp_len)
        {
            int ok = 0;
            if(tmp[tmp_len-1] < i) ok = 1;
            for(int j = len[to_n][to_k] - 1;!ok && j>=0;j--)
            {
                if(d[to_n][to_k][j] > tmp[j])
                {
                    ok = 1;
                    break;
                }
            }
            if(ok)
            {
                tmp[tmp_len - 1] = i;
                for(int j = tmp_len-2;j>=0;j--)
                    tmp[j] = d[to_n][to_k][j];
            }
        }
        /*printf("n = %d,k = %d,i = %d,tmp_len = %d,to_n = %d,to_k = %dn",k,tmp_len,to_n,to_k);
        for(int j = tmp_len-1;j>=0;j--)
            printf("%d",tmp[j]);
        puts("");*/
    }
    len[n][k] = tmp_len;
    if(tmp_len != -1)
        for(int i = 0;i<tmp_len;i++)
            d[n][k][i] = tmp[i];

    /*if(len[n][k]!=-1)
    {
        printf("******** n = %d,tmp_len = %dn",tmp_len);
        for(int i = len[n][k]-1;i>=0;i--)
            printf("%d",d[n][k][i]);
        puts("");
    }*/
}

int main()
{
    int cas = 0;
    int n;
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d",&m);
        memset(vis,sizeof(vis));
        dfs(n,0);
        printf("Case %d: ",++cas);
        if(len[n][0] == -1)
            puts("-1");
        else
        {
            int pos = len[n][0]-1;
            while(d[n][0][pos] == 0 && pos > 0) pos --;
            for(int i = pos;i>=0;i--)
                printf("%d",d[n][0][i]);
            puts("");
        }
    }
    return 0;
}