uva 12105——Bigger is Better

╰半夏微凉° 2022-08-18 02:41 11阅读 0赞

题意：给定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);
    		}
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019，Done is better than perfect

2018年已经结束，很多小伙伴们已经开始计划2019年的目标，当大家兴致勃勃的立下Flag时，往往这个时候就会出现一个“讨厌”的人（或者是自己内心的想法），他会很严肃的问你：

╰+攻爆jí腚メ/ 2023年06月13日 09:10/ 0 赞/ 131 阅读

相关 NetFlow Vs. sFlow: Which is better?

最近主要工作精力在BGP方面，BGP环境搭建好后又上了DDos高防，所以需要配置sFlow，NetFlow；以下是网上关于NetFlow，sFlow的讲解，转载以作学习记录

系统管理员/ 2023年06月12日 08:47/ 0 赞/ 19 阅读

相关 HDU 1856 -More is better

并查集rank数组 Description Mr Wang wants some boys to help him with a project. Because

本是古典何须时尚/ 2022年08月21日 11:58/ 0 赞/ 16 阅读

相关 uva 12105——Bigger is Better

题意：给定n个火柴，求能够摆出的最大的数。思路：递推，dp（i，j）表示i根火柴拼出除以m余数为j的最大的数，然后递推用dp（i，j）\10+k更新dp（i+mp

╰半夏微凉°/ 2022年08月18日 02:41/ 0 赞/ 12 阅读

相关 UVA 10131 Is Bigger Smarter? 【严格单调递增子序列】

题目：[UVA 10131Is Bigger Smarter][] 题意：给出大象的身高和体重，求身高递增且体重递减的最长序列，都是严格的，并打印序列。

àì夳堔傛蜴生んèń/ 2022年08月12日 01:59/ 0 赞/ 125 阅读

相关 2019，Done is better than perfec

2018年已经结束，很多小伙伴们已经开始计划2019年的目标，当大家兴致勃勃的立下Flag时，往往这个时候就会出现一个“讨厌”的人（或者是自己内心的想法），他会很严肃的问你：

冷不防/ 2022年03月30日 06:42/ 0 赞/ 138 阅读

相关 D - More is better

题目描述： Mr Wang wants some boys to help him with a project. Because the project is rath

缺乏、安全感/ 2022年03月19日 11:26/ 0 赞/ 126 阅读

相关 Worse Is Better 思想的发展史

> 从历史的发展的角度看问题才能接近问题的真相。本文主要翻译自Richard P. Gabriel对于Worse is Better思想发展的自述。原文链接：[http

蔚落/ 2022年03月07日 13:56/ 0 赞/ 164 阅读

相关 More is better(并差集)

More is better Problem Description Mr Wang wants some boys to help him with a project

叁歲伎倆/ 2022年02月25日 13:14/ 0 赞/ 149 阅读

相关 UVA 12105 Bigger is Better（数位DP）

题意：![å¨è¿éæå¥å¾çæè¿°][70] 分析：方法一：很容易想到，dp\[i\]\[j\]代表用了i根火柴，除m余j的最大数。用刷表法，每次选择一个数

╰+哭是因爲堅強的太久メ/ 2021年12月15日 00:57/ 0 赞/ 198 阅读