解题报告_韩霖.htm

集合了SOJ（四川大学ACM在线评测系统）众多经典题目的详细解题报告

1151&nbsp;&nbsp;&nbsp;&nbsp;解&nbsp;&nbsp;题&nbsp;&nbsp;报&nbsp;&nbsp;告<br>														韩霖<br>	这道题说的是给你一个Piggy&nbsp;Bank可以往里面放硬币。然后告诉你它装硬币前和装硬币后的<br>质量E,&nbsp;F，以及硬币的种类N，每种硬币的质量W和面值P。然后求Piggy&nbsp;Bank在给定的E，F条<br>件下最少能装多少面额的硬币。<br>	这是一道动规的题，很像。我的具体做法是先用一个整型变量iWheight&nbsp;=&nbsp;F&nbsp;–&nbsp;E，表示硬币<br>的总质量，然后开一个数组Wheight[&nbsp;100001&nbsp;]，Wheight[&nbsp;n&nbsp;]&nbsp;表示当硬币质量为n时的最少<br>面额。给Wheight的第零个元素赋值为0，其它元素赋值为-1，表示当前找不到满足条件的硬币<br>组合。用一个iCoin[&nbsp;5000&nbsp;][&nbsp;2&nbsp;]存放硬币的信息，iCoin[&nbsp;n&nbsp;][&nbsp;0&nbsp;]表示第n种硬币的面值，<br>iCoi[&nbsp;n&nbsp;][&nbsp;1&nbsp;]表示第n种硬币的质量。然后可以知道Wheight[&nbsp;m&nbsp;]与前面元素的关系为Whei<br>ght[&nbsp;m&nbsp;]&nbsp;=&nbsp;Min(&nbsp;Wheight[&nbsp;m&nbsp;–&nbsp;iCoin[&nbsp;0,1……N&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;+&nbsp;iCoin[&nbsp;0,1……N&nbsp;][&nbsp;0&nbsp;]&nbsp;)<br>&nbsp;。最后，如果Wheight[&nbsp;iWheight&nbsp;]&nbsp;==&nbsp;-1，则输出&nbsp;”&nbsp;This&nbsp;is&nbsp;impossible.&nbsp;”，否则输出<br>Wheight[&nbsp;iWheight&nbsp;]的值。源代码如下：<br>#include&nbsp;&lt;stdio.h&gt;<br>int&nbsp;main()<br>{<br>	long&nbsp;int&nbsp;T,&nbsp;E,&nbsp;F,&nbsp;Weight[&nbsp;100001&nbsp;],&nbsp;P,&nbsp;W,&nbsp;n,&nbsp;m,&nbsp;iWeight,&nbsp;N,&nbsp;iCoin[&nbsp;5000&nbsp;][&nbsp;2&nbsp;],&nbsp;<br>a,&nbsp;iMin;<br>	scanf&nbsp;(&quot;%ld&quot;,&nbsp;&amp;T);<br>	for&nbsp;(n&nbsp;=&nbsp;0;&nbsp;n&nbsp;&lt;&nbsp;T;&nbsp;n++)<br>	{<br>		for&nbsp;(m&nbsp;=&nbsp;0;&nbsp;m&nbsp;&lt;=&nbsp;10000;&nbsp;m++)<br>			Weight[&nbsp;m&nbsp;]&nbsp;=&nbsp;-1;<br>		scanf&nbsp;(&quot;%ld%ld&quot;,&nbsp;&amp;E,&nbsp;&amp;F);<br>		iWeight&nbsp;=&nbsp;F&nbsp;-&nbsp;E;<br>		scanf&nbsp;(&quot;%ld&quot;,&nbsp;&amp;N);<br>		for&nbsp;(m&nbsp;=&nbsp;0;&nbsp;m&nbsp;&lt;&nbsp;N;&nbsp;m++)<br>			scanf&nbsp;(&quot;%d%d&quot;,&nbsp;&amp;iCoin[&nbsp;m&nbsp;][&nbsp;0&nbsp;],&nbsp;&amp;iCoin[&nbsp;m&nbsp;][&nbsp;1&nbsp;]);<br>		Weight[&nbsp;0&nbsp;]&nbsp;=&nbsp;0;<br>		for&nbsp;(m&nbsp;=1&nbsp;;&nbsp;m&nbsp;&lt;=&nbsp;iWeight;&nbsp;m++)<br>		{<br>			iMin&nbsp;=&nbsp;300000000;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;&nbsp;&nbsp;&nbsp;注意iMin的初值<br>			for&nbsp;(a&nbsp;=&nbsp;0;&nbsp;a&nbsp;&lt;&nbsp;N;&nbsp;a++)<br>			{<br>				if&nbsp;(m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;&gt;=&nbsp;0)<br>				{<br>					if&nbsp;(Weight[&nbsp;m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;!=&nbsp;-1)<br>						if&nbsp;(iMin&nbsp;&gt;&nbsp;Weight[&nbsp;m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;+&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;0&nbsp;])<br>							iMin&nbsp;=&nbsp;Weight[&nbsp;m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;+&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;0&nbsp;];<br>				}<br>			}<br>			if&nbsp;(iMin&nbsp;!=&nbsp;300000000)<br>				Weight[&nbsp;m&nbsp;]&nbsp;=&nbsp;iMin;<br>		}<br>		if&nbsp;(Weight[&nbsp;iWeight&nbsp;]&nbsp;&gt;&nbsp;0)<br>			printf&nbsp;(&quot;The&nbsp;minimum&nbsp;amount&nbsp;of&nbsp;money&nbsp;in&nbsp;the&nbsp;piggy-bank&nbsp;is&nbsp;%d.\n&quot;,&nbsp;Weight[&nbsp;iWei<br>ght&nbsp;]);<br>		else<br>			printf&nbsp;(&quot;This&nbsp;is&nbsp;impossible.\n&quot;);<br>	}<br>	return&nbsp;0;<br>}<br>还有一点值得注意。请注意iMin的初值。我当时开始给iMin的初值为30000，因为我以前做类<br>似的题一直都用的30000。结果这道题测试数据过了，可提交上去老WA&nbsp;。后来才发现根据题中<br>E,&nbsp;F和W,&nbsp;P的取值范围，硬币的总面额是有可能大于30000的，30000不能大于Wheight[&nbsp;n&nbsp;]所<br>有的可能值，就会发生错误。后来，把iMin的初值改为300000000后，就AC了。这道题再一次<br>提醒了我，有时候经验很重要，但不能完全凭经验，还要根据具体的题意来做题，不能疏忽大<br>意。<br><font style='font-size:12pt'>
<br>
==============================================<br>
<a target=_blank href='http://vip.163.com' title='http://vip.163.com'><font color=green><b>安全稳定大容量，收费伊妹儿免费30日完美体验~</b></a><br>
<a target=_blank href='http://mail.163.com' title='http://mail.163.com'><font color=red><b>中国最大的免费邮箱在等你 25兆空间 4兆附件！</b></a><br>
<a target=_blank href='http://popo.163.com' title='http://popo.163.com'><font color=green><b>点击网易泡泡惊喜无限 全免费手机短信任你发!</b></a><br><br>