题意:现在要写m行代码,总共有n个文件,现在给出第i个文件每行会出现v[i]个bug,问你在bug少于b的条件下有多少种安排
分析:定义dp[i][j][k],i个文件,用了j行代码,有k个bug
状态转移为
1.在第i个文件,不写代码 dp[i][j][k]=dp[i-1][j][k]
2.在第i个文件,写代码 dp[i][j][k]+=dp[i][j-1][k-v[i]]
这题巧妙在于,既往i转移,又往j和k方向转移,这样我把它形容为二维动态规划
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=500+10;
ll dp[maxn][maxn],num[maxn];
int main()
{
ios::sync_with_stdio(false);
int n,m,b,mod;
cin>>n>>m>>b>>mod;
for(int i=1;i<=n;i++)
cin>>num[i];
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
int v=num[i];
for(int j=1;j<=m;j++)
for(int k=v;k<=b;k++)
dp[k][j]=(dp[k][j]+dp[k-v][j-1])%mod;
}
ll ans=0;
for(int i=0;i<=b;i++)
ans=(ans+dp[i][m])%mod;
cout<<ans<<endl;
return 0;
}