SRM 585

250 :
左下から右下に1本、残りはサブ構造
 

const int mod =  1000000007;

long long dp[1000010] , s[1000010];

class 

TrafficCongestion{

    public :

    int theMinCars(int n) {

        long long ans = 0;

        dp[0] = 1;

        dp[1] = 1; s[0] = 1; s[1] =2;

        REP(i,2,n) {

            dp[i] = (1 + s[i-2] + s[i-2] ) % mod;

            s[i] = (s[i-1] + dp[i]) % mod;

        }

        return dp[n];

    }

};

500pt:
 
小さいから大きいまでn種類の数字の個数をあげて、すべての数字からなるシーケンスのlisnum=kの数を判断させます.lisnumはシーケンスが増加するセグメント数です
dp[i][j]は、前のi種数がj個のlisnumの数を生成し、i+1種数を置く際にそれらのインクリメントセグメントの後ろにいくつかの数を列挙して置く必要があることを示す.このようにしてlisnumの数を増やすことはなく、t個数をインクリメントセグメントの後ろに置くと仮定する
では現在sum+1-j+t個の位置がlisnumを増やすので、残りのcnt[i+1]-t個の数をこれらの位置に置くのが高校の仕切り法です
 

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

typedef long long lld;

const int mod = 1000000007;

int dp[2][1500];

int C[1500][1500];

class LISNumber {

    public :

    int count(vector <int> cnt, int K) {

        C[0][0] = 1;

        for(int i = 1; i < 1500; i++) {

              C[i][0] = C[i][i] = 1;

             for(int j = 1; j < i; j++) {

                  C[i][j] = C[i-1][j] + C[i-1][j-1];

                  if(C[i][j] >= mod) C[i][j] -= mod;

             }

        }

        dp[0][cnt[0]] = 1; int sum=cnt[0];

        for(int i = 1; i < cnt.size(); i++) {

            memset(dp[i&1],0,sizeof(dp[0]));

            for(int j = 0; j <= K; j++) if(dp[(i-1)&1][j]) {

                for(int t = 0; t <= min(cnt[i],j); t++) {

                    int box = sum + 1 - j + t;

                    int balls = cnt[i] - t;

                    dp[i&1][j+balls] += (lld)dp[(i-1)&1][j] * C[j][t] % mod * C[box-1+balls][balls] % mod;

                    if(dp[i&1][j+balls] >= mod) dp[i&1][j+balls] -= mod;

                }

            }

            sum+=cnt[i];

        }

        return dp[(cnt.size()-1)&1][K];

    }

};





// Powered by FileEdit

// Powered by TZTester 1.01 [25-Feb-2003]

// Powered by CodeProcessor