UVA 12105 Bigger is Better（数位DP）-蒲公英云

UVA 12105 Bigger is Better（数位DP）

" class="reference-link">题意：

分析：方法一：很容易想到，dp[i][j]代表用了i根火柴，除m余j的最大数。用刷表法，每次选择一个数k放在最右边，用dp[i][j]×10+k去更新dp[i+needs[k]][ ( j×10+k) % m]，其中needs[i]：i 所需要的火柴个数。不过因为有100个火柴，会涉及到大数。计算量挺大。方法二：不好想。定义状态(i,j)表示用不超过i根火柴拼出“除以m余数为j”的整数的最大长度。设dp(i,j)。p(i,j)记录满足状态(i,j)的整数的最高位数字。转移方程：dp(i,j) = max{ dp(i-needs[k] , (j10+k)%m)+ } ( i >= needs[k] )。上述方程表示当我们从高位往低位写数字的时候，假设当前写的数字是x,高位的数字除以m的余数为j，那么把x添加到前面写过的数字后面时候，相当于先对前一次写出来的数10，然后加上x，那么这个新数的余数就是(j10+x)%m。由于dp值表示的位数，因此我们取位数最大的那个dp值，然后+1，就是状态(i,j)的最大长度，同时更新状态(i,j)对应的那个数字x，又因为我们希望写出的数尽可能的大，因此枚举x的h时候要从大到小枚举，而且必须满足c[x]<=i，其中c[x]表示写出数字x需要使用的火柴数。

注意一个优化点，由于高精度的计算上只需要乘10+k，常规的高精度乘法复杂度还是有点高会超时，所以用数组去模拟，每次*10 + k的时候就往后多一位即可。

参考：https://blog.csdn.net/cy05627/article/details/88748079、https://blog.csdn.net/corncsd/article/details/19929257。

代码（方法一）：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAXN 110
#define MAXM 3010
using namespace std;
int N,M;
int v[10]={6,2,5,5,4,5,6,3,7,6};
char dp[MAXN][MAXM][60],ans[60],s[60];
int compare(char *a,char *b){
    int la=strlen(a),lb=strlen(b);
    if(la>lb) return 1;
    else if(la<lb) return -1;
    return strcmp(a,b);
}
void DP(char *a,char *b,int k){
    strcpy(s,b);
    int l=strlen(s);
    if(l==1&&s[0]=='0'){
        s[l-1]='0'+k;
        s[l]=0;
    }
    else{
        s[l]='0'+k;
        s[l+1]=0;///等价于 s[l+1]='\0'
    }
    if(compare(s,a)>0) strcpy(a,s);
}
int main(){
    int cas=0;
    while(scanf("%d",&N),N){
        scanf("%d",&M);
        memset(dp,0,sizeof(dp));/// 等价于 全部字符初始化为'\0';
        dp[0][0][0]='0';
        for(int i=0;i<=N;i++)
            for(int j=0;j<M;j++) if(strlen(dp[i][j])>0){///触发更新的条件
                for(int k=0;k<10;k++) DP(dp[i+v[k]][(j*10+k)%M],dp[i][j],k);///前面的状态更新后面的状态
            }
        ans[0]=0;
        for(int i=N;i>0;i--) if(compare(ans,dp[i][0])<0) strcpy(ans,dp[i][0]);
        printf("Case %d: ",++cas);
        if(ans[0]==0) puts("-1");
        else puts(ans);
    }
    return 0;
}

LRJ代码（方法二）：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
const int maxm = 3000 + 5;
// dp[i][j] is the maximal length of the integer whose remainder is j (with at most i matches)
// p[i][j] is the maximal digit for state (i,j)
// p[i][j]表示这个数首位是什么
int n, m, dp[maxn][maxm], p[maxn][maxm];
int needs[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
int main()
{
    int kase = 0;
    while(scanf("%d%d", &n, &m) == 2)
    {
        printf("Case %d: ", ++kase);
        // 预处理
        for(int i = 0; i <= n; i++)
            for(int j = 0; j < m; j++)
            {
                int& ans = dp[i][j];
                ans = p[i][j] = -1;
                if (j == 0) ans = 0;
                for(int d = 9; d >= 0; d--)
                    if (i >= needs[d])
                    {
                        int t = dp[i - needs[d]][(j * 10 + d) % m];
                        if (t >= 0 && t + 1 > ans) //t exist
                        {
                            ans = t + 1;
                            p[i][j] = d;
                        }
                    }
            }
        if (p[n][0] < 0) printf("-1");
        else
        {
            int i = n, j = 0;
            for(int d = p[i][j]; d >= 0; d = p[i][j])
            {
                printf("%d", d);
                i -= needs[d];
                j = (j * 10 + d) % m;
            }
        }
        printf("\n");
    }
    return 0;
}