티스토리 뷰

알고리즘 관련/BOJ

BOJ)12019 동아리방 청소!

JASON 자손9319 2017. 2. 17. 17:04

문제:icpc.me/12019


동아리방에 사람들이 들어올때마다 더러움이 누적되고 사람들은 더러움만큼 불쾌함을 느끼게 될 때 N일동안 딱 M번만 청소가 가능하다. N일 동안 들어온 사람 수가 주어질 때 사람들이 느끼는 총 불쾌함의 최솟값을 구하는 문제이다.


우리는 다이나믹 프로그래밍을 통하여 답을 구해줄 수 있다. 근데 불쾌함을 계산할때 (그날 들어온 사람 수) x (누적 된 더러움) 이므로 더러움을 날마다 들어오는 사람들의 수의 psum을 통하여 관리해준다. 그리고 psum으로 누적 된 더러움을 계산할 때 그날까지의 psum - 청소한 날의 psum으로 계산해줘야 하기 때문에 dp테이블에 마지막으로 청소한날을 가지고 가야한다.


따라서 dp 테이블은 dp[pos][state][last] 가 되며 의미는 pos~n일 까지 m-state번 청소하였을 때 최솟값 이때 last는 마지막으로 청소한 날이다.


점화식은 

dp[x][y][z]=(psum[pos]-psum[last])*a[pos+1] +min(dp[pos+1][state][last],dp[pos+1][state+1][pos+1])이 된다.


역추적을 해줘야 하기 때문에 min부분에서 작은 값을 따로 저장하여 역추적 해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define INF 987654321
using namespace std;
int dp[101][11][101], psum[101], a[101], n, m;
pair<int, pair<intint>> back[101][11][101];
vector<int> vt;
int func(int pos, int state, int last) {
    if (state > m)return INF;
    if (pos == n + 1)
        return 0;
    int &ret = dp[pos][state][last];
    if (ret != -1)return ret;
    ret = (psum[pos] - psum[last])*a[pos + 1];
    int x = func(pos + 1, state, last);
    int y = func(pos + 1, state + 1, pos + 1);
    if (x < y)
        back[pos][state][last] = { pos + 1,{ state,last } };
    else
        back[pos][state][last] = { pos + 1,{ state + 1,pos + } };
    return ret += min(x, y);
}
int main() {
    memset(dp, -1sizeof(dp));
    scanf("%d%d"&n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d"&a[i]);
        psum[i] = psum[i - 1+ a[i];
    }
    printf("%d\n", func(000));
    int x, y, z;
    x = y = z = 0;
    vt.push_back(0);
    while (x != n + 1) {
        if (vt.back() != z)
            vt.push_back(z);
        int a, b, c;
        a = x, b = y, c = z;
        x = back[a][b][c].first;
        y = back[a][b][c].second.first;
        z = back[a][b][c].second.second;
    }
    if (n == m)
        for (int i = 1; i <= n; i++)
            printf("%d ", i);
    else
        for (int i = 1; i < vt.size(); i++)
            printf("%d ", vt[i]);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1017 소수 쌍  (0) 2017.02.20
BOJ)13560 Football  (0) 2017.02.20
BOJ)12019 동아리방 청소!  (0) 2017.02.17
BOJ)1671 상어의 저녁식사  (0) 2017.02.16
BOJ)1867 돌멩이 제거  (0) 2017.02.16
BOJ)11377 열혈강호3  (0) 2017.02.16
댓글
댓글쓰기 폼