UVA11375【火柴拼数Matches】-------2015年1月27日
一：题意描述
本题主要是讲给定n个火柴，用这n个火柴去拼数，问最后可以拼成多少种？
二：问题分析
我们需要找出状态：假设当我们把已经使用的火柴数i当做一个状态。当i=0时，我们从这个状态可以转化成状态2（数字1），3（数字7），4（数字4），5（数字2,3,5），6（数字6,9（数字0此时不行）），7（数字8）。当i不等于0时，我们可以从这个状态转化成状态(i+2)（数字1），(i+3)（数字7），(i+4)（数字4），(i+5)（数字2,3,5），(i+6)（数字0,6,9（这里可以包括0）），(i+7)（数字8）。
分析到这里，我们首先用公式定义状态：
dp[i]:使用了i个火柴可以拼凑的数字数目
dp[i+c[j]]+=dp[i];
那么最后的种数等于dp[1]+dp[2]+·····+dp[n]。当n>=6时我们还需要增加1表示数字0.
三：AC代码
#include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; #define maxn 2000+10 int c[10]={6,2,5,5,4,5,6,3,7,6}; long long dp[maxn]; void process() { memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=0;i<maxn;i++) for(int j=0;j<10;j++) { if(!(i==0&&j==0)&&(i+c[j]<maxn)) dp[i+c[j]]+=dp[i]; } } int main() { process(); int n; while(cin>>n) { long long sum=0; for(int i=1;i<=n;i++) sum+=dp[i]; if(n>=6) cout<<sum+1<<endl; else cout<<sum<<endl; } return 0; }