首页 > 代码库 > Poj 1742 Coins

Poj 1742 Coins

题意:

  给定N个面值,a1..an,每种面值都有c1..cn个,问从1..m的面值中,有多少个可以用已经给定的面值组成?

 

分析:

   还记得“多重组合数”问题么?

   DP[K][N]——用前N种数字组成K,第N种可以剩下最多多少个。

   证明分析就不给出了,见前面的博文吧。时间复杂度为K*N

 

这道题有点意思的地方就是,给定的几个限制,在空间上,时间上都需要很注意,不然很容易超出。

这里面的M的范围为100000,N为100。

 

空间限制为300000K,int型数组开100000*100的话,刚好超出一点,为了简单方便,我们使用&1优化(奇偶优化),使得空间复杂度变为10000*2.

时间上,用G++交的话会超时....——目前不太明白。

C++交的,最后是2903ms过的,刚好...

Poj 1742 Coins