SRM 585

250 ：

遞推，從左下角到右下角走一條，剩下的都是子結構

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]; 
    } 
}; 

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 

#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