SOJ1151 解 题 报 告

SOJ1151    解  题  报  告
韩霖
这道题说的是给你一个Piggy Bank可以往里面放硬币。然后告诉你它装硬币前和装硬币后的
质量E, F，以及硬币的种类N，每种硬币的质量W和面值P。然后求Piggy Bank在给定的E，F条
件下最少能装多少面额的硬币。
这是一道动规的题，很像。我的具体做法是先用一个整型变量iWheight = F – E，表示硬币
的总质量，然后开一个数组Wheight[ 100001 ]，Wheight[ n ] 表示当硬币质量为n时的最少
面额。给Wheight的第零个元素赋值为0，其它元素赋值为-1，表示当前找不到满足条件的硬币
组合。用一个iCoin[ 5000 ][ 2 ]存放硬币的信息，iCoin[ n ][ 0 ]表示第n种硬币的面值，
iCoi[ n ][ 1 ]表示第n种硬币的质量。然后可以知道Wheight[ m ]与前面元素的关系为Whei
ght[ m ] = Min( Wheight[ m – iCoin[ 0,1……N ][ 1 ] ] + iCoin[ 0,1……N ][ 0 ] )
 。最后，如果Wheight[ iWheight ] == -1，则输出 ” This is impossible. ”，否则输出
Wheight[ iWheight ]的值。源代码如下：
#include <stdio.h>
int main()
{
long int T, E, F, Weight[ 100001 ], P, W, n, m, iWeight, N, iCoin[ 5000 ][ 2 ], 
a, iMin;
scanf ("%ld", &T);
for (n = 0; n < T; n++)
{
for (m = 0; m <= 10000; m++)
Weight[ m ] = -1;
scanf ("%ld%ld", &E, &F);
iWeight = F - E;
scanf ("%ld", &N);
for (m = 0; m < N; m++)
scanf ("%d%d", &iCoin[ m ][ 0 ], &iCoin[ m ][ 1 ]);
Weight[ 0 ] = 0;
for (m =1 ; m <= iWeight; m++)
{
iMin = 300000000;                 //    注意iMin的初值
for (a = 0; a < N; a++)
{
if (m - iCoin[ a ][ 1 ] >= 0)
{
if (Weight[ m - iCoin[ a ][ 1 ] ] != -1)
if (iMin > Weight[ m - iCoin[ a ][ 1 ] ] + iCoin[ a ][ 0 ])
iMin = Weight[ m - iCoin[ a ][ 1 ] ] + iCoin[ a ][ 0 ];
}
}
if (iMin != 300000000)
Weight[ m ] = iMin;
}
if (Weight[ iWeight ] > 0)
printf ("The minimum amount of money in the piggy-bank is %d.\n", Weight[ iWei
ght ]);
else
printf ("This is impossible.\n");
}
return 0;
}
还有一点值得注意。请注意iMin的初值。我当时开始给iMin的初值为30000，因为我以前做类
似的题一直都用的30000。结果这道题测试数据过了，可提交上去老WA 。后来才发现根据题中
E, F和W, P的取值范围，硬币的总面额是有可能大于30000的，30000不能大于Wheight[ n ]所
有的可能值，就会发生错误。后来，把iMin的初值改为300000000后，就AC了。这道题再一次
提醒了我，有时候经验很重要，但不能完全凭经验，还要根据具体的题意来做题，不能疏忽大
意。