题意:给你一棵高度为H的完全二叉树的路,问最少需要多少辆车把这路走完,车子不能返回。
那么最优的方案就是从小到上一层层的走完,就很容易地可以得到一种递推,需要注意的就是dp[0] = 1
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime> using namespace std; class TrafficCongestion {
public:
int theMinCars(int);
};
#define LL long long
const int mod = 1000000007;
LL dp[1000005];
int TrafficCongestion::theMinCars(int n) {
dp[0] = 1;
dp[1] = 1;
LL pre = 2;
for(int i = 2;i <= n; i++) {
dp[i] = dp[i-2] + pre;
dp[i] %= mod;
pre = pre*2%mod;
}
return dp[n];
}
给你0到n-1每种数字的数量,问你能构成k个严格递增的序列的方案有多少种,结果对mod取余。
那我们用dp[i][j] 表示放了前i种数字构成j个严格递增的序列的种数,接下来要放第i+1个数字,这里cnt代表前i个数的总数,cur代表i+1的个数,对于j个序列要放 L 个i+1在后面,那剩下的i+1能放的地方有cnt-j+1,剩下i+1的个数为cur-L。我们把cnt-j+1简化成a,cur-L简化成b。
问题就转化成在a个地方放b个东西的方案数,有些地方可以不放东西,那我们就人为地加上a个东西,现在就有a+b个东西了,用a-1的隔板就可以把a+b个东西分成a份,每份中至少有1个东西,可以选择的插隔板的地方有a+b-1个。这就相当于在a个地方放b个东西且有些地方可以不放东西!经典的隔板法!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define LL long long using namespace std; class LISNumber {
public:
int count(vector <int>, int);
}; LL c[1505][1505], dp[38][1505];
const int mod = 1000000007;
int LISNumber::count(vector <int> card, int K) {
int i, j, l;
c[0][0] = 1;
for(i = 1;i <= 1500; i++) {
c[i][0] = 1;
for(j = 1;j <= i; j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod;
}
memset(dp, 0, sizeof(dp));
dp[0][card[0]] = 1;
int cnt = card[0];
for(i = 1;i < card.size(); i++) {
int cur = card[i];
for(j = 1;j <= K; j++) {
if(!dp[i-1][j]) continue;
for(l = 0;l <= j; l++) if(cur + j - l <= K && cur >= l)
dp[i][cur-l+j] = (dp[i][cur-l+j] + dp[i-1][j]%mod*c[j][l]%mod*c[cnt+cur-j][cur-l])%mod ;
}
cnt += cur;
}
return dp[card.size()-1][K];
}