【Java】【高精度】【递推】UVA - 11375 - Matches

Z时代
2024-01-10
分类：综合

java

d[i+c[j]]+=d[i]（c[j]是拼成j所需的火柴数）

d[0]=1；

别忘了不能有前导零，所以当i为零时，不要尝试去拼成零。反而应该在n>=6时，最后给答案加1（单独拼出0）。

import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
	static BigInteger[] d=new BigInteger[2010];
	static int[] c=new int[]{6,2,5,5,4,5,6,3,7,6};
	public static void main(String[] argc){
		Scanner sc = new Scanner (new BufferedInputStream(System.in));
		while(sc.hasNext()){
			Arrays.fill(d,BigInteger.ZERO);
			int n=sc.nextInt();
			d[0]=BigInteger.ONE;
			for(int i=0;i<=n;++i){
				for(int j=0;j<10;++j){
					if((i!=0 || j!=0) && i+c[j]<=n){
						d[i+c[j]]=d[i+c[j]].add(d[i]);
					}
				}
			}
			BigInteger ans=BigInteger.ZERO;
			for(int i=1;i<=n;++i){
				ans=ans.add(d[i]);
			}
			if(n>=6){
				ans=ans.add(BigInteger.ONE);
			}
			System.out.println(ans);
		}
		sc.close();
    }
}