【题目描述】 kkk某天闲得无聊，给自己规定，要用最多N根火柴摆出一个尽量大的正整数，而且这个数要能够被M整除。 【输入格式】 两个整数N和M 【输出格式】 拼出的数，无解输出-1 【样例输入】 6 3 【样例输出】 111 【数据范围】 1<=N<=100 1<=M<=3000 【分析】 一般来说，整数是从左往右一位一位写的，因此不难想到这样的DP算法：设f[i][j]表示用i根火柴能拼出的模m值为j的最大数，枚举在最右边添加的数字k，用f[i][j]*10+k来更新f[i+c[k],(j*10+k)%m]，其中的c[k]是常量数组，表示拼出数字k需要的火柴数。
const maxn=101; maxm=3001; match:array[0..9]of integer=(6,2,5,5,4,5,6,3,7,6); var i,j,k,n,m,t,ans:longint; f,p:array[0..maxn,0..maxm]of longint; begin read(n,m); for i:=0 to n do for j:=0 to m-1 do begin p[i,j]:=-1; f[i,j]:=-1; ans:=-1; if j=0 then begin ans:=0;f[i,j]:=0; end; for k:=9 downto 0 do if i>=match[k] then begin t:=f[i-match[k],(j*10+k) mod m]; if (t>=0)and(t+1>ans) then begin ans:=t+1; f[i,j]:=t+1; p[i,j]:=k; end; end; end; if p[n,0]<0 then writeln(-1) else begin i:=n;j:=0; k:=p[i,j]; while k>=0 do begin write(k); i:=i-match[k]; j:=(j*10+k) mod m; k:=p[i,j]; end; writeln; end; end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533514.html
