[伯俊]2662企業投資
白駿2662企業投資
https://www.acmicpc.net/problem/2662
dpから最大収益を簡単に得ることができますが、企業ごとの投資額を出力するのは少し難しいです.
https://www.acmicpc.net/problem/2662
dpから最大収益を簡単に得ることができますが、企業ごとの投資額を出力するのは少し難しいです.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 300;
const int MAXM = 20;
int n,m;
//[company][money]
int profit[MAXM+1][MAXN+1];
int cache[MAXM + 1][MAXN + 1];
int bestChoice[MAXM + 1][MAXN + 1] = { 0 };
int getMaxProfit(int company, int money) {
if (company > m || money == 0) return 0;
int& ret = cache[company][money];
if (ret != -1) return ret;
//투자하지 않는 경우
int choice = 0;
ret = getMaxProfit(company + 1, money);
//1만원 ~ 가지고 있는 돈만큼 투자하는 경우
for (int i = 1; i <= money; ++i) {
int cand = profit[company][i] + getMaxProfit(company + 1, money - i);
if (ret < cand) {
ret = cand;
choice = i;
}
}
bestChoice[company][money] = choice;
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(cache, -1, sizeof(cache));
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
int money;
cin >> money;
for (int j = 1; j <= m; ++j)
cin >> profit[j][i];
}
cout << getMaxProfit(1,n)<<"\n";
int sumOfChoice = 0;
for (int i = 1; i <= m; ++i) {
int choice = bestChoice[i][n - sumOfChoice];
cout << choice << " ";
sumOfChoice += choice;
}
return 0;
}
Reference
この問題について([伯俊]2662企業投資), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-2662-기업-투자テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol