URAL 1513. Lemon Tale 好多大数

dp[ i ][ j ]表示长度 i ，末尾连续 j 个L的方案数。

dp[ i ][ 0 ] ?= sigma dp[ i - 1 ][ j ] (0 <= j && j <= min(i-1,m));

dp[ i ][ j ] = dp[ i-1 ][ j-1 ] ( j != 0 && j <= min(i,m));

这是最简单明了的递推式子，可是时间复杂度为o?(n*m),显然难以胜任。

通过对式子观察，第 dp[ i ] 对于 dp[ i-1 ]只多了 dp[ i ][ 0 ]这一项，也就是说我们需要计算只有dp[ i ][0]这一项，且dp[ i ][ 0 ] =?sigma dp[ i - 1 ][ j ] (0 <= j && j <= min(i-1,m));

显然我们可以用栈将整个dp[ ][ ] 优化成一维数组。

若 m == 0,初始栈只有一个元素 1，否则初始栈有两个元素1,1。

我们只有需要计算n-2次栈顶的 k = min(Top,m) 项和即可。Top为栈中的元素个数。

此时，时间复杂度为 o（n）。

因为有大数只能用Java来写了. . . . . .幸好没用到复杂的数据结构=,=

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,m,t,i,j;
        
        n = cin.nextInt();   
        m = cin.nextInt();    
        
        BigInteger []dp = new BigInteger[10002];
        
        
        
        int con = 1,Top;
        
        dp[0] = BigInteger.ONE;
        
        BigInteger ans = BigInteger.ZERO;
        
        if(m >= 1)
        {
        	dp[1] = BigInteger.ONE;
        	Top = 2;
        	ans = ans.add(dp[0].add(dp[1]));
        }
        else
        {
        	Top = 1;
        	ans = ans.add(dp[0]);
        }
        
        dp[Top] = ans;
        
        Top++;
        
        for(i = 2;i <= n; ++i)
        {
        	if(con < m)
        	{
        		ans = ans.add(ans);
        		con++;
        	}
        	else
        	{
        		ans = ans.add(ans);
        		ans = ans.subtract(dp[Top-m-2]);
        	}
        	dp[Top] = ans;
    		Top++;
        }
        
        System.out.println(dp[Top-1]);
    }
}