HDU - 2929 Bigger is Better

제목: 당신의 임무는 n개의 성냥을 초과하지 않고 최대한 큰 성냥을 놓아서 m에 의해 정제될 수 있는 정수, 무해시 출력-1
사고방식: n개의 성냥을 초과하지 않고 배열할 수 있는 최대수가 몇 자리인지 미리 처리한다. 그러면 이 수가 m의 배수일수록 그의 자릿수가 커야 쓸모가 있다. 그러면 1차원으로 여수를 기록한다. 그래서 dp[i][j]는 i뿌리로 구성된 여수가 j의 최대 자릿수이고 그 다음은 각 자릿수를 인쇄하는 것이다. 만족하는 조건을 생각해 보자.
dp[i][j]+1=dp[newi][newj]가 만족한다면 dp[newi][newj]가 존재한다면 새로 추가된 K가 바로 다음이다.next[i][j]로 현재 상태의 다음 수를 표시한다

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;
const int MAXM = 3010;
const int used[10] = {6,2,5,5,4,5,6,3,7,6};

int dp[MAXN][MAXM],next[MAXN][MAXM];
int n,m,maxlen;

int main(){
    int cas = 0;
    while (scanf("%d",&n) != EOF && n){
        scanf("%d",&m);
        memset(dp,-1,sizeof(dp));
        dp[0][0] = 0,maxlen = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (dp[i][j] >= 0)
                    for (int k = 9; k >= 0; k--)
                        if (i + used[k] <= n){
                            int newi = i+used[k],newj = (j*10+k)%m;
                            if (dp[i][j] + 1 > dp[newi][newj]){
                                dp[newi][newj] = dp[i][j] + 1;
                                if (dp[newi][newj] > maxlen && newj == 0)
                                    maxlen = dp[newi][newj];
                            }
                        }
        memset(next,-1,sizeof(next));
        for (int i = n; i >= 0; i--)
            for (int j = 0; j < m; j++)
                if (dp[i][j] >= 0){
                    if (dp[i][j] == maxlen && j == 0){
                        next[i][j] = 10;
                        continue;
                    }
                    for (int k = 9; k >= 0; k--){
                        if (i + used[k] <= n){
                            int newi = i + used[k];
                            int newj = (j*10+k)%m;
                            if (dp[newi][newj] == dp[i][j] + 1 && next[newi][newj] >= 0){
                                next[i][j] = k;
                                break;
                            }
                        }
                    }
                }
        printf("Case %d: ",++cas);
        int i,j,u,v;
        if (maxlen > 0){
            i = 0,j = 0;
            while (next[i][j] != 10){
                u = i + used[next[i][j]];
                v = (j*10+next[i][j]) % m;
                printf("%d",next[i][j]);
                i = u,j = v;
            }
            printf("
");
        }
        else if (n >= used[0])
                printf("0
");
             else printf("-1
");
    }
    return 0;
}