Problem B: 擺花

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?41??Solved:?27
[Submit][Status][Web Board]

Description

小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共m盆。通過調(diào)查顧客的喜好，小明列出了顧客最喜歡的n種花，從1到n標(biāo)號(hào)。為了在門口展出更多種花，規(guī)定第i種花不能超過ai盆，擺花時(shí)同一種花放在一起，且不同種類的花需按標(biāo)號(hào)的從小到大的順序依次擺列。
試編程計(jì)算，一共有多少種不同的擺花方案。

Input

? ? ? ?第一行包含兩個(gè)正整數(shù)n和m，中間用一個(gè)空格隔開。
第二行有n個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，依次表示a1、a2、……an。

Output

輸出只有一行，一個(gè)整數(shù)，表示有多少種方案。注意：因?yàn)榉桨笖?shù)可能很多，請輸出方案數(shù)對1000007取模的結(jié)果。

Sample Input

2 43 2

Sample Output

2

HINT

?　　對于100%數(shù)據(jù)，有0<n≤100，0<m≤100，0≤ ai≤100。

題解：動(dòng)態(tài)規(guī)劃? ? 呃呃呃，對于這個(gè)，作為菜鳥的我一概不，只知道動(dòng)態(tài)規(guī)劃是對前面情況的最優(yōu)下對當(dāng)前情況的影響，

? ? ? ?太菜太菜。。。。

這里引用了別人到解析。

仔細(xì)研究了很久，為了保證擺的花不超過規(guī)定的盆數(shù)，在擺第i種花時(shí)擺花的盆數(shù)不能超過min(a [ i ] , j ?)盆（j 表示還有幾盆花要擺），在不超過限制的情況下擺一盆花的方案數(shù)為min( a[ i ] , j )，擺兩盆花時(shí)的方案數(shù)f[n][2]+=f[n-1][2-k](k從0~min(a[i],2))。所以就得到動(dòng)態(tài)轉(zhuǎn)移方程f[i][j]+=f[i-1][j-k](0<=k<=min(a[i],j)).

代碼：

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<list> #include<algorithm> using namespace std; const int mod=1000007;int main() {int a[105],f[105][105]; int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=0;i<=a[1];i++)f[1][i]=1;for(int i=2;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<=min(j,a[i]);k++)f[i][j]=(f[i][j]+f[i-1][j-k])%mod;printf("%d",f[n][m]); }

總結(jié)

以上是生活随笔為你收集整理的zcmu-2108的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。