TIOJ 1628 組合布丁

    又是個DP呵呵(本人超愛DP)
首先,我們把所有的口味排序,然後找出每種口味有幾個
假設共a種口味 而每種有xi個(Σxi=k)

然後就來定義狀態:
dp[i][j]表示前i種口味取j個的取法數

而第i種口味有xi個 所以它的數量是

轉移方程:dp[i][j]=dp[i-1][j-0]+dp[i-1][j-1]+dp[i-1][j-2]......dp[i-1][j-xi];
(第i種口味有 0個的數量 + 1個的 + 2個的......)
而邊界條件很簡單dp[0][0]=1;

這樣大致上就完成了
然後再把二維陣列壓成一維就好,使用滾動數組
以下是我的code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,k,m;
ll dp[2][5010];
ll pud[5010];
vector<pll> typ;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
while(cin>>n>>k>>m){
for(int i=0;i<n;i++)
cin>>pud[i];
sort(pud,pud+n);
typ.clear();
//判斷每種有幾個
typ.push_back({pud[0],1});
int si=0; //vector的大小
for(int i=1;i<n;i++){
if(pud[i]==typ[si].first)
typ[si].second++;
else{
typ.push_back({pud[i],1});
si++;
}
}
si++;
//重複利用 pud 只存每種有幾個
for(int i=0;i<si;i++)
pud[i]=typ[i].second;

memset(dp,0,sizeof dp);
//第0列表示計算至前一種布丁的狀態
//第1列表示當下要計算的第l種布丁

dp[0][0]=1; //第前0種取0個的方法數是1
for(int l=0;l<si;l++){
for(int i=1;i<=k;i++){
for(int j=0;j<=pud[l];j++){
if(i-j<0)
break;
dp[1][i]+=dp[0][i-j];
dp[1][i]%=m;
}
}
//存回去上一列
for(int i=1;i<=k;i++){
dp[0][i]=dp[1][i];
dp[1][i]=0;
}
}
cout<<dp[0][k]<<'\n';
}
}