uva 12105——Bigger is Better-蒲公英云

uva 12105——Bigger is Better

题意：给定n个火柴，求能够摆出的最大的数。

思路：递推，dp（i，j）表示i根火柴拼出除以m余数为j的最大的数，然后递推用dp（i，j）*10+k更新dp（i+mp（k），（j*10+K）%m）；lrj说大数精度问题，java乱搞搞过。。

code：

import java.util.*;
import java.math.BigInteger;
public class Main
{
    public static void main(String args[])
    {
        Scanner cin=new Scanner(System.in);
        int mp[]={6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
        BigInteger dp[][]=new BigInteger[105][3005];
        int ca=0;
        while (cin.hasNextInt()){
            int n=cin.nextInt();
            if (n==0) break;
            int m=cin.nextInt();
            BigInteger ans=BigInteger.valueOf(-1);
            for (int i=0;i<=n;i++) 
                for (int j=0;j<m;j++)
                    dp[i][j]=BigInteger.valueOf(-1);
            dp[0][0]=BigInteger.valueOf(0);
            for (int i=0;i<=n;i++){
                for (int j=0;j<m;j++){
                    if (dp[i][j].compareTo(BigInteger.valueOf(-1))==0) continue;
                    for (int k=0;k<10;k++){
                        if (i+mp[k]>n) continue;
                        BigInteger b=dp[i][j].multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(k));
                        if (dp[i+mp[k]][(j*10+k)%m].compareTo(b)==-1)
                            dp[i+mp[k]][(j*10+k)%m]=b;
                    }
                }
            if (i>=2&&ans.compareTo(dp[i][0])==-1) ans=dp[i][0];
            }            
            ca++;
            System.out.println("Case "+ca+": "+ans);
        }
    }
}