这题难在找到题中隐含的递推关系,假设当n = k的时候有s中情况,那么当n = k + 1时,若新增加的一元钱化成两张5角,那么一共有s种情况,再把其中的一张5角化掉,增加(n * 10 - 5)/ 2 +1种情况,再化掉剩下的一张5角,增加(n*10/2)+1种情况,整理可得n = k + 1时,结果为s + (n * 10 - 5)/ 2 +1 + (n*10/2)+1 = s + n * 10 - 1种情况,递推关系出来了,剩下的就好办了。
直接打表。
#include <stdio.h> int a[101] = {0, 10}; int main(){ int t, n; for(n = 2; n != 101; ++n) a[n] = a[n - 1] + n * 10 - 1; scanf("%d", &t); while(t-- && scanf("%d", &n)) printf("%d\n", a[n]); return 0; }
原文:http://blog.csdn.net/chang_mu/article/details/20164699