题意:有n个人写m行代码,第i个人写一行代码会产生ai个bug,问bug小于b的方案数
思路:背包二维费用
AC代码:
#include "iostream"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#define ll long long#define bug(x) cout<<<" "<<"UUUUU"< >n>>m>>b>>mod; for(int i=1; i<=n; ++i){ cin>>a[i]; } for(int i=1; i<=n; ++i) for(int k=1; k<=m; ++k){ for(int j=a[i]; j<=b; ++j){ dp[k][j]=dp[k-1][j-a[i]]+dp[k][j]; dp[k][j]%=mod; } } ll ans=0; for(int i=0; i<=b; ++i){ ans+=dp[m][i]; ans%=mod; } cout<<(ans+mod)%mod<