但是比賽完之后一看，竟然是dp。。例如前幾天的口號匹配求方案數(shù)的題目，今天的uva4656，以及hdu4248都是這種類型的題目。。
說說uva4565吧。
題意大概意思是：有N種紙牌，G給位置。。然后給定每種紙牌最少排幾張，求滿足的方案。
這樣一來我們怎么劃分狀態(tài)呢？以位置？
不，我們得用紙牌來劃分狀態(tài)，并枚舉紙牌之前用了幾張
那么用f[i][j]表示前I個(gè)紙牌已經(jīng)滿足題意，且總共放了j個(gè)位置的方案數(shù)。那么 f[i][j] = sigma（f[i-1][k] * c[G - k][j - k]）{j - k >= a[i]}
至于為什么是 f[i-1][k] * c[G - k][j - k]，我們可以這樣理解：
反正總的位置固定，選取的j-k個(gè)在剩下的G-k個(gè)里選擇位置就行了。。（這樣不會有問題吧）
hdu4248:
這一題自己懶得寫了，轉(zhuǎn)自這個(gè)博客http://www.cnblogs.com/sweetsc/archive/2012/07/17/2595189.html
我覺得寫得很不錯(cuò)！
題意：有N種石頭，每種石頭有A1，A2....AN個(gè)，現(xiàn)取出一些石頭組成序列，求可以組成多少種序列
例如：3種：可以產(chǎn)生：B; G; M; BG; BM; GM; GB; MB; MG; BGM; BMG; GBM; GMB; MBG; MGB.
我們采用動(dòng)態(tài)規(guī)劃的思想，劃分階段：按照石頭種類劃分階段。于是乎，咱們對于第i種石頭，相當(dāng)于之前石頭的顏色并不重要，借助高中數(shù)學(xué)插板法的思想，假如之前的i - 1 種石頭，拼出了長 度為len，那么，相當(dāng)于有l(wèi)en + 1個(gè)空，咱們要放第 i 種石頭進(jìn)去，于是乎，轉(zhuǎn)化成了經(jīng)典問題，我比較得意的總結(jié)：
| 球和球 | 盒和盒 | 空盒 | 情況數(shù) |
| 有區(qū)別 | 有區(qū)別 | 有空盒 | m^n |
| 有區(qū)別 | 有區(qū)別 | 無空盒 | M！s（n,m） |
| 有區(qū)別 | 無區(qū)別 | 有空盒 | S(n,1)+s(n,2)+…+s(n,m),n>=m |
| S(n,1)+s(n,2)+…+s(n,n),n<=m | |||
| 有區(qū)別 | 無區(qū)別 | 無空盒 | S(n,m) |
| 無區(qū)別 | 有區(qū)別 | 有空盒 | C(n+m-1,n) |
| 無區(qū)別 | 有區(qū)別 | 無空盒 | C(n-1,m-1) |
| 無區(qū)別 | 無區(qū)別 | 有空盒 | DP |
| 無區(qū)別 | 無區(qū)別 | 無空盒 | DP |
這里，第 i 種石頭互相沒有區(qū)別，len + 1個(gè)空有序，相當(dāng)于有區(qū)別，可以有空盒，于是，如果咱們從第 i 種中放put個(gè)進(jìn)去，情況數(shù)應(yīng)該是 C(put + len , put)
于是設(shè)計(jì)狀態(tài)：DP[i][j] 表示 用前 i 種石頭，排出長度為 j 的可能數(shù)
然后，狀態(tài)轉(zhuǎn)移的時(shí)候，枚舉在階段 i 放入put個(gè)，DP[i + 1][j + put] += DP[i][j] * C(put + j, put) 即可
附上自己奇丑無比的代碼：
Uva4656
重慶分公司
重慶分公司
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MXN 50100
#define Inf 101010
#define M0(a) memset(a, 0, sizeof(a))
using namespace std;
double c[36][36], f[36][36];
int a[50], sum[50];
int n, m;
void init(){
M0(c);
for (int i = 0; i <= 33; ++i)
c[i][0] = 1;
for (int i = 1; i <= 33; ++i)
for (int j = 1; j <= i; ++j)
c[i][j]= c[i-1][j] + c[i-1][j-1];
}
void solve(){
M0(sum);
M0(f);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i){
scanf("%d", &a[i]);
sum[i]= sum[i-1] + a[i];
}
f[0][0] = 1;
for (int i = 1; i <= m; ++i)
for (int j = sum[i]; j <= n; ++j){
for (int k = a[i]; k <= j; ++k)
f[i][j]+= f[i-1][j-k] * c[n - j + k][k];
}
for (int i = 1; i <= n; ++i)
f[m][n]/= m;
printf("%.6lf
", f[m][n] * 100.00);
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out","w", stdout); int T, cas = 0;
scanf("%d", &T);
init();
for (int i = 1; i <= T; ++i){
printf("Case #%d:", i);
solve();
}
// fclose(stdin); fclose(stdout);} hdu4248
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MXN 50100
#define Inf 101010
#define P 1000000007
#define M0(a) memset(a, 0, sizeof(a))
using namespace std;
int c[10100][102];
long long f[102][10100];
int n, a[110], m, sum[110];
void init(){
for (int i = 0; i <= 10010; ++i)
c[i][0] = 1;
for (int i = 1; i <= 10010; ++i)
for (int j = 1; j <= 101 && j <= i; ++j)
c[i][j]= (c[i-1][j] + c[i-1][j-1]) % P;
}
void solve(){
m= 0;
M0(f);
M0(sum);
for (int i = 1; i <= n; ++i){
scanf("%d", &a[i]);
m+= a[i];
sum[i]= m;
}
f[0][0] = 1;
long long ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= sum[i]; ++j){
for (int k = 0; k <= a[i]; ++k){
if (k > j) break;
f[i][j]= (f[i][j] + f[i-1][j-k] * c[j][k]) % P;
}
if (i == n && j) ans = (ans + f[i][j]) % P;
}
printf("%I64d
", ans);
}
int main(){
//freopen("a.in", "r", stdin);
// freopen("a.out","w", stdout); int T, cas = 0;
init();
while (scanf("%d", &n) != EOF){
printf("Case %d:", ++cas);
solve();
}
fclose(stdin); fclose(stdout);
} 
