<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
我们知道人民币有1、2、5、10、20、50、100这几种面值。 
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。 
比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
输入有多组，每组一行，为一个整合n。 
输入以0结束。
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
输出该面额有几种表示方法。
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
1 
4 
0
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
1 
3
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
类似于<a href="/post/AOJ/808.html">&gt;AOJ 808.算法期末考试D(整数拆分)&lt;</a> 
最初想用完全背包问题求解,不过由于还要保证使用的钱数不超过 <code>100</code> ,可以用 <code>DFS</code> 来计算
由于只有 <code>1~205</code> ,可以使用打表法来输出
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
using namespace std;

const int money[] = {1,2,5,10,20,50,100};

const int ans[] = {0,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34,41,44,51,54,61,68,75,82,89,96,109,116,129,136,149,162,175,188,201,214,236,249,271,284,306,328,350,372,394,416,451,473,508,530,565,600,635,670,705,740,793,828,881,916,969,1022,1075,1128,1181,1234,1311,1364,1441,1494,1571,1648,1725,1802,1879,1956,2064,2141,2249,2326,2434,2542,2650,2758,2866,2974,3121,3229,3376,3484,3631,3778,3925,4072,4219,4366,4563,4709,4905,5051,5247,5442,5637,5832,6027,6221,6476,6669,6924,7116,7369,7622,7875,8127,8378,8628,8954,9202,9526,9772,10094,10415,10735,11054,11371,11686,12093,12406,12810,13119,13520,13920,14318,14713,15106,15497,15998,16384,16880,17262,17754,18243,18729,19212,19692,20169,20776,21246,21847,22311,22905,23495,24081,24663,25240,25812,26539,27103,27821,28375,29083,29786,30483,31174,31859,32538,33398,34065,34913,35567,36401,37228,38048,38859,39662,40458,41465,42245,43234,43997,44970,45933,46885,47828,48762,49686,50851,51754,52899,53781,54903,56013,57111,58197,59271,60332,61671,62705,64018,65026,66309,67578,68833,70073,71296,72503,74029,75206,76699,77839,79297,80738,82159,83562,84944,86308,88035,89360,91045,92327,93970,95593,97191,98768,100318,101850,103791,105272,107162,108595,110434,112250,114034,115795,117525,119231,121396,123044,125152,126740,128786,130806,132787,134743,136660,138547,140953};

int v;

int num;
void DFS(int a,int pos,int cnt) {
 if(a &lt; 0 || cnt&gt;100)
 return;
 if(a == 0 ) {
 num++;
 return;
 }
 int tMoney = money[pos];

 if(pos &lt; 0)
 return;

 for(int j = a / tMoney;j &gt;= 0;j--) {
 DFS(a - j * tMoney,pos - 1,cnt + j);

 }
}

bool Do() {
 scanf(&#34;%d&#34;,&amp;v);
 if(v == 0)
 return false;
 /*
 num = 0;
 DFS(v,sizeof(money) / sizeof(int) - 1,0);

 printf(&#34;%d\n&#34;,num);
 */
 printf(&#34;%d\n&#34;,ans[v]);
 return true;
}

int main() {
 /*
 for(int i = 1;i &lt;= 250;i++) {
 num = 0;
 DFS(i,sizeof(money) / sizeof(int) - 1,0);
 printf(&#34;%d,&#34;,num);
 }
 */
 while(Do());
 return 0;
}
</pre>

AOJ 169.找零钱