[TIOJ 1471][ZJ b177] 山景 Skyline

作法：

記 dp[ i ][ j ] 是「走了 i 步且目前高度為 j ，且從此之後一直往下走到底是一條合法路徑」的路徑總數，就可以遞推得出了。但每次要算 dp[ i ][ j ] 的時候，會發現他其實會是一塊三角形(或是被砍一角的三角形)裡面的點的 dp 值總和，總不能一個一個加，所以會需要多維護兩個 sum 的陣列，一個代表 dp[ i ][ j ] +dp[ i-1 ][ j-1] +...  的值，一個代表 dp[ i ][ j ] + dp[ i+1 ][ j-1 ] +... 的值，就可以維護那塊三角形裡的數的總和，O(1)轉移。但這樣會爆記憶體，我只好丟建表的 code QQ ( 直接開一個 ans[ 1501 ] = { 答案們 }  )。

還有一點很陰險，就是他要的是輸出後 9 位，所以 >= 10^8 的數都會需要補0，小於的就不用，我傳上 ZJ 才知道還有這招QQ

code :

#include<bits/stdc++.h>
#define MOD 1000000000
const int maxn=3000+10 ;
 
int sum1[maxn][maxn],sum2[maxn][maxn] ;
 
main()
{
    int n,s ; scanf("%d",&n) ;
    int ans=0 ;
    for(int i=1;i<=n;i++) for(int j=0;j<=n;j++)
    {
        if(j>i)
        {
            s=(s+sum1[i][j-1])%MOD ;
            s-= (j>=2*i+1) ? sum2[i][j-2*i-1] : sum2[j-i-1][0] ;
            s=(s%MOD+MOD)%MOD ;
        }
 
        if(i>j || ((i+j)%2))
        {
            sum1[i][j]= (j ? sum1[i-1][j-1] : 0) ;
            sum2[i][j]=sum2[i-1][j+1] ;
            continue ;
        }
 
        if(i==j)
        {
            s=0 ;
            sum1[i][j]=(sum1[i-1][j-1]+1)%MOD ;
            sum2[i][j]=(sum2[i-1][j+1]+1)%MOD ;
            if(i+j==n) ans++ ;
            continue ;
        }
 
        if(i+j==n) ans=(ans+s)%MOD ;
        sum1[i][j]=(sum1[i-1][j-1]+s)%MOD ;
        sum2[i][j]=(sum2[i-1][j+1]+s)%MOD ;
    }
    if(n<=50) printf("%d\n",ans) ;
    else printf("%09d\n",ans) ;
}