d645 - 輪下亡魂
題目描述
題目描述了鴨子在被車撞死後，鴨神給予牠第二次機會，這次的挑戰是最大化鴨子的飽足感。鴨子有一定胃容量，可以選擇不同種類的飼料。飼料有飽足感、體積和類型。飼料類型包括：神的鴨飼料（無限次使用）、普通鴨飼料（只能使用一次）和分身鴨飼料（可以被吃特定次數）。目標是找到在胃容量限制下，鴨子可以獲得的最大飽足感。
解題思路
本題可以使用動態規劃來解決。定義 c[j][i] 為考慮前 i 種飼料，且胃容量為 j 時的最大飽足感。對於每種飼料，我們需要考慮是否選擇它。如果選擇了該飼料，則需要減去其體積，並加上其飽足感。對於神的鴨飼料，可以無限次選擇，因此需要遍歷所有可能的選擇次數。對於分身鴨飼料，則需要遍歷其允許的最大選擇次數。普通鴨飼料只能選擇一次。最終，答案是所有可能的胃容量中，c[j][a] 的最大值，其中 a 是飼料種類數。
複雜度分析
- 時間複雜度: O(b * a * max_t * 1000)，其中 b 是鴨子胃的容量，a 是飼料種類數，max_t 是分身鴨飼料的最大次數。
- 空間複雜度: O(b * a)，用於儲存動態規劃表格。
程式碼
#include <iostream>
using namespace std;
int main(){
int a,b,v,w,t;
while(cin >> a >> b){
int c[b+1][a+1],ans=0;
for(int i=0;i<=a;++i){
for(int j=0;j<=b;++j){
c[j][i]=0;
}
}
for(int i=0;i<a;++i){
cin >> v >> w >> t;
for(int j=b;j>=0;--j){
if(j==0||c[j][i]!=0){
if(t==-1){
for(int k=0;j+w*k<=b;++k)
c[j+w*k][i+1]=max(c[j+w*k][i+1],max(c[j][i]+v*k,c[j+w*k][i]));
}
else{
for(int k=0;k<=t&&j+w*k<=b;++k)
c[j+w*k][i+1]=max(c[j+w*k][i+1],max(c[j][i]+v*k,c[j+w*k][i]));
}
}
}
}
for(int j=b;j>=0;--j){
if(c[j][a]>ans){
ans=c[j][a];
}
}
cout << ans << "\n";
}
}