Description

Input

Output

Sample Input

樣例一：3 2 1
樣例二：15 6 4

Sample Output

樣例一：10
樣例二：458177764

Data Constraint

Hint

樣例一解釋：

Solution

• 對于這種求方案數的問題，我們考慮DP。

• 我們考慮逐個位置填區間，比如說做到了第 ii 個容器。

• 那么在填了的區間（設共有 jj 個）中，肯定有些已經閉合了，有些尚未閉合（設為 kk 個）。

• 那么我們就得到了狀態 f[i][j][k]f[i][j][k] 表示此時的方案數，顯然 f[0][0][0]=1f[0][0][0]=1 。

• 如何轉移呢？我們想想這時我們可以做什么，閉合某些尚未閉合的區間，開啟新的未閉合的區間。

• 于是我們枚舉兩個值 dec,incdec,inc 分別表示此時閉合區間的數量和將要開啟新區間的數量。

• 由于這 KK 個區間是互不相同的，我們要需要處理出其順序帶來的方案數。

• 那么顯然有轉移式：f[i][j][k]?Cdeck?Cincj+inc=>f[i+1][j+inc][k?dec+inc]f[i][j][k]?Ckdec?Cj+incinc=>f[i+1][j+inc][k?dec+inc]

• 其中 CdeckCkdec 表示在 kk 個未閉合的區間中選擇 decdec 來閉合增加的組合方案。

• 而 Cincj+incCj+incinc 表示新增的 incinc 個區間在總共的 j+incj+inc 個區間中的排列順序增加的組合方案。

• 而每個容器的容量為 TT 的限制就相當于在任意時刻未閉合的區間數量不超過 TT 。

• 答案即為 f[n+1][k][0]f[n+1][k][0] 。

• 時間復雜度 O(NK4)O(NK4) 。

Code

#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int N=45,mo=1011110011; int n,k,T; int f[N][N][N],c[N][N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } int main() {freopen("container.in","r",stdin);freopen("container.out","w",stdout);n=read(),k=read(),T=read();for(int i=0;i<N;i++) c[i][0]=1;for(int i=1;i<N;i++)for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;f[0][0][0]=1;for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)for(int l=0;l<=j && l<=T;l++)if(f[i][j][l])for(int inc=0;j+inc<=k;inc++)for(int dec=0;dec<=l;dec++)if(l-dec+inc<=T)f[i+1][j+inc][l-dec+inc]=(f[i+1][j+inc][l-dec+inc]+(LL)f[i][j][l]*c[l][dec]%mo*c[j+inc][inc]%mo)%mo;printf("%d",f[n+1][k][0]);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5192. 【NOI2017模拟7.2】容器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。