Bigger is Better
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1106 Accepted Submission(s): 278
Problem DescriptionBob has n matches. He wants to compose numbers using the following scheme (that is, digit 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 needs 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 matches):
Write a program to make a non-negative integer which is a multiple of m. The integer should be as big as possible. InputThe input consists of several test cases. Each case is described by two positive integers n (n ≤ 100) and m (m ≤ 3000), as described above. The last test case is followed by a single zero, which should not be processed. OutputFor each test case, print the case number and the biggest number that can be made. If there is no solution, output -1.Note that Bob don’t have to use all his matches. Sample Input6 3
5 6
0 Sample OutputCase 1: 111
Case 2: -1 Source2006 Asia Regional Xi-An
题意:要用最多N根火柴摆出一个尽量大的正整数,而且这个数要能够被M整除洛谷U5033
一开始想d[i][j]表示i根火柴模m后为j的最大数字然后想会溢出然后想用高精怎么样然后想高精慢,可以把d[i][j]的值分解成k*m+j,保存k和j就行了,结果并不好转移然后搜了一下题解 用d[i][j]表示i根火柴拼成数字模m后为j有几位初始化-1不可行,d[0][0]=0用更新的写法,因为/10总感觉有点悬
d[i+ms[k]][(j*+k)%m]这样dp完了之后再处理每一位是什么,用bit[i][j]表示,n倒着枚举
具体的思想就是,大到小枚举k,找[i][j]第一个能更新到的"合法的"[ti][tj]
对于d[i][j]==mxl,bit[i][j]=10代表这一位最高下面没有了最后打印方案,从尾开始,因为每次加是加在最后
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=,M=,INF=1e9;
int n,m;
int ms[]={,,,,,,,,,},d[N][M],bit[N][M];
void dp(){
int mxl=;
memset(d,-,sizeof(d));
d[][]=;
for(int i=;i<=n;i++)
for(int j=;j<m;j++) if(d[i][j]>=){
for(int k=;k<=;k++) if(i+ms[k]<=n){
if(d[i+ms[k]][(j*+k)%m]<d[i][j]+)
d[i+ms[k]][(j*+k)%m]=d[i][j]+;
//if(i==0&&j==0) printf("o %d %d %d\n",i+ms[k],(j*10+k)%m,d[i+ms[k]][(j*10+k)%m]);
}
if(j==) mxl=max(mxl,d[i][j]);//printf("d %d %d %d\n",i,j,d[i][j]);
} memset(bit,-,sizeof(bit));
for(int i=n;i>=;i--)
for(int j=;j<m;j++) if(d[i][j]>=){
if(d[i][j]==mxl&&j==) {bit[i][j]=;continue;}
for(int k=;k>=;k--) if(i+ms[k]<=n){
int ti=i+ms[k],tj=(j*+k)%m;
if(d[ti][tj]==d[i][j]+&&bit[ti][tj]>=) {bit[i][j]=k;break;}
// if(i==0&&j==0) printf("obit %d %d %d %d\n",ti,tj,d[ti][tj],bit[ti][tj]);
}
}
//printf("hi %d %d %d\n",mxl,d[0][0],bit[0][0]);
if(mxl>){
int i=,j=,ti,tj;
while(mxl-->){
ti=i+ms[bit[i][j]];
tj=(j*+bit[i][j])%m;
printf("%d",bit[i][j]);
i=ti;j=tj;
}
}else printf("-1");
printf("\n");
}
int main(){int cas=;
while(cin>>n){ if(n==) break;cin>>m;
printf("Case %d: ",++cas);
dp();
}
}