題意：
集團里有 n 名員工，他們可以完成各種各樣的作業創造利潤，
第 i 種作業會產生 profit[i] 的利潤，它要求 group[i] 名成員共同參與，
如果成員參與了其中一項作業，就不能參與另一項作業，
作業的任何至少產生 minProfit 利潤的子集稱為 盈利計劃 ，
并且作業的成員總數最多為 n ，
有多少種計劃可以選擇？因為答案很大，所以 回傳結果模 10^9 + 7 的值，
1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100
解法：
令d[i][j][k]表示前i種作業,一共用了j個人,收益為k的方案數,
注意當收益>=minProfit時是等價的,因此當收益>=minProfit時,令其=minProfit即可.
轉移方程:
設當前作業需要x個人,收益為y,
1.如果不做當前作業,則d[i+1][j][k]+=d[i][j][k]
2.如果做當前作業,且j+x<=n,則d[i+1][j+x][min(k+y,mi)]+=d[i][j][k];
code：
const int mod=1e9+7;
int d[111][111][111];
class Solution {
public:
int profitableSchemes(int n, int mi, vector<int>& a, vector<int>& b) {
int p=a.size();
memset(d,0,sizeof d);
d[0][0][0]=1;
for(int i=0;i<p;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=mi;k++){
if(!d[i][j][k])continue;
d[i+1][j][k]=(d[i+1][j][k]+d[i][j][k])%mod;
int j1=j+a[i],k1=min(k+b[i],mi);
if(j1<=n){
d[i+1][j1][k1]=(d[i+1][j1][k1]+d[i][j][k])%mod;
}
}
}
}
int ans=0;
for(int j=0;j<=n;j++){
ans=(ans+d[p][j][mi])%mod;
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286712.html
標籤：其他
上一篇：環信即時通訊專案——有源代碼
下一篇：質量分析工具-監控大廳大揭秘