71883113137761
状态转移方程:dp[i][j] = dp[i-1][j]+dp[1][j-(1~3)] (d[0][0] = 1);
代码:
#include <stdio.h>#include <string.h>#define MAX 35000int dp[MAX] ;int main(){int n;while(scanf("%d",&n) != EOF){memset(dp,0,sizeof(int)*(n+10)) ;dp[0] = 1 ;for(int i = 1 ; i <= 3 ; ++i){for(int j = i ; j <= n ; ++j)dp[j] = dp[j]+dp[j-i] ;}printf("%d\n",dp[n]) ;}return 0 ;}
呵呵,,再附送你们一个神代码(不是我写的):#include<stdio.h>int main(){int n,sum,i;while(scanf("%d",&n)!=EOF){int t=n/3+1;//3分的个数sum=0;for(i=0;i<t;i++){sum+=(n-i*3)/2+1;}printf("%d\n",sum);}return 0;}因为本题的钱币数只有1,2,3三种,所以令t=n/3,然后遍历一遍i从0到t,,代表面值为三分的个数,然后用总价值减去三分硬币所代表的价值,用这个值除以2,得到的数就是每确定一个三分的数值后对应的2分的硬币的兑换总数。最后再加上全部为1分的情况,就是所求的解了。
下面的代码简直是碉堡了。
深重如溺入蓝色的海洋,无法呼吸。