UVA 11375 - Matches (数学——递推)

题意：用n跟火柴能组成多少个非负整数，其中火柴不必用完。其中

0——6根火柴

1——2根火柴

2——5根火柴

3——5根火柴

4——4根火柴

5——5根火柴

6——6根火柴

7——3根火柴

8——7根火柴

9——6根火柴

题解：采用递推，从前到后依次添加数字，注意当为0的时候不能添加0。

从状态i到状态i+c[x]，c[x]表示数字x需要的火柴数。

还有一点要注意的是，数字可能非常大，所以要用高精度来做。

AC代码：(Java)

import java.util.Scanner;  
import java.math.*;  
  
public class Main  
{  
    static final int N=2010;  
    static Scanner cin=new Scanner(System.in);  
    static BigInteger one=BigInteger.ONE,zero=BigInteger.valueOf(0);;  
    public static void main(String[] args)  
    {  
        // TODO Auto-generated method stub  
        BigInteger []d=new BigInteger[N];  
        BigInteger []f=new BigInteger[N];  
        int []c=new int[11];  
        c[1]=2;  
        c[7]=3;  
        c[4]=4;  
        c[2]=c[3]=c[5]=5;  
        c[0]=c[6]=c[9]=6;  
        c[8]=7;  
          
        for(int i=1;i<N;i++)  
            d[i]=zero;  
        d[0]=one;  
          
        for(int i=0;i<N;i++)  
            for(int j=0;j<10;j++)  
                if(!(i==0&&j==0)&&(i+c[j])<=2000)  
                {  
                    d[i+c[j]]=d[i+c[j]].add(d[i]);  
                }  
        f[0]=zero;  
        for(int i=1;i<=2000;i++)  
            f[i]=f[i-1].add(d[i]);  
        while(cin.hasNext())  
        {  
            int n=cin.nextInt();  
            if(n<6)  
                System.out.println(f[n]);  
            else  
                System.out.println(f[n].add(one));//n大于6时，包括0，所以要加一  
        }  
    }  
  
}

补充：软件开发 , Java ,