-
Notifications
You must be signed in to change notification settings - Fork 0
Open
Labels
studyStudyStudy
Description
Problem link
https://atcoder.jp/contests/abc080/tasks/abc080_c
Problem Summary
상점을 오픈하는데, 특정 시간에 다른 상점이 열린 개수에 따라 최대로 만들 수 있는 이익을 구하는 문제.
Fij : i 상점이 j 시간에 열려 있는지 여부.
Pij : i 상점이 j 시간만큼 열린 시간이 겹쳤을 때 얻을 수 있는 이익.
Solution
처음에 문제 자체를 이해하기 좀 어려웠는데 계속 보니까 대략 머리에 들어왔다.
일단, Joisino가 상점을 열지 말지 두 가지 방법이 있고 시간이 총 10개 있으므로 단순 2^10 탐색을 해주면 된다.
상점을 열었을 경우 그 시점에 다른 상점이 열려있는 개수를 카운트 하고 더해주면 되는 간단한 문제.
Source Code
#include <iostream>
using namespace std;
int f[100][10];
int p[100][11];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 10; j++)
{
cin >> f[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 11; j++)
{
cin >> p[i][j];
}
}
int ans = -1987654321;
for (int i = 1; i < (1 << 10); i++)
{
int profit = 0;
for (int j = 0; j < n; j++)
{
int cnt = 0;
for (int k = 0; k < 10; k++)
{
// open
if (i & (1 << k) && f[j][k] == 1)
{
cnt++;
}
}
profit += p[j][cnt];
}
ans = max(ans, profit);
}
cout << ans << endl;
}
Metadata
Metadata
Assignees
Labels
studyStudyStudy