UVA 12105 Bigger is Better（数位DP）

╰+哭是因爲堅強的太久メ 2021-12-15 00:57 187阅读 0赞

## 题意：![å¨è¿éæå¥å¾çæè¿°][70] ##

## 分析：   方法一：很容易想到，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\] , (j\*10+k)%m)+ \} ( i >= needs\[k\] )。   上述方程表示当我们从高位往低位写数字的时候，假设当前写的数字是x,高位的数字除以m的余数为j，那么把x添加到前面写过的数字后面时候，相当于先对前一次写出来的数10，然后加上x，那么这个新数的余数就是(j\*10+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_cy05627_article_details_88748079]、[https://blog.csdn.net/corncsd/article/details/19929257][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;
    }

[70]: /images/20211214/3af10c3efb1b4b2096c4445b8fb19c70.png
[https_blog.csdn.net_cy05627_article_details_88748079]: https://blog.csdn.net/cy05627/article/details/88748079
[https_blog.csdn.net_corncsd_article_details_19929257]: https://blog.csdn.net/corncsd/article/details/19929257