URAL 1513. Lemon Tale(简单的递推)

写几组数据就会发现规律了啊。。可是我是竖着看的。。。还找了半天啊、、、

不过要用高精度来写，水题啊，就当熟悉一下java了啊。

num[i] = 2*num[i-1]-num[i-2-k]。

1513. Lemon Tale

5 2

24

import java.math.BigInteger;
import java.util.Scanner;



public class Main {



	public static void main(String[] args) {

		Scanner cin = new Scanner(System.in);
		int n, k;
		BigInteger num[] = new BigInteger [100005];
		while(cin.hasNext())
		{
			n = cin.nextInt();
			k = cin.nextInt();
			BigInteger ans;
			BigInteger p = BigInteger.valueOf(2);
			ans = p.pow(n);
			if(k == 0)
			{
				System.out.println(1);
				continue;
			}
			if(n == k)
			{
				System.out.println(ans);
				continue;
			}
			num[0] = BigInteger.valueOf(1);
			for(int i = 1; i <= k+1; i++) 
			{
				num[i] = p.pow(i-1);
			}
			for(int i = k+2; i <= n; i++)
			{
				num[i] = num[i-1].multiply(BigInteger.valueOf(2));
				num[i] = num[i].subtract(num[i-2-k]);
			}
			ans = BigInteger.valueOf(0);
			for(int i = n; i >= (n-k); i--)
			{
				ans = ans.add(num[i]);
			}
			System.out.println(ans);
		}
	}
}

URAL 1513. Lemon Tale(简单的递推)

原文：http://blog.csdn.net/xu12110501127/article/details/39968117