#53299: 一維處理的方式
411435030@gms.ndhu.edu.tw
(呱呱嘎嘎)
學校
:
不指定學校
編號 : 317327
來源 : [134.208.58.9]
最後登入時間 ：
2025-09-03 23:44:04
先以金額建議一個陣列，以dp[j] = 戰力 ， j= 花費的金額 ，並做一個暫存去紀錄 {金額，戰力}
在一直去取max 更新陣列
以下程式給各位參考
#include<bits/stdc++.h>
using namespace std;
int main(){
int m,n,p;
cin >> m>> n >>p;
vector<int> dp(m+1,-1);
dp[0] = 0;
for(int i=0;i<n;i++)
{
vector<pair<int ,int >> player;
for(int i=1;i<=p;i++)
{
int a,b;
cin >> a>>b;
player.push_back({a,b});
}
vector<int> newdp = dp;
for(auto pp : player)
{
int cost = pp.first;
int power = pp.second;
//cout << cost<<" "<< power<<endl;
for(int j=0;j+cost<=m;j++)
{
if(dp[j] != -1) newdp[j+cost] = max(newdp[j+cost], dp[j] + power);
}
}
dp = newdp;
}
cout<< *max_element(dp.begin(), dp.end());
return 0;
}