BOJ)12019 동아리방 청소!

문제: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부분에서 작은 값을 따로 저장하여 역추적 해주면 된다.

#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<int, int>> 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 + 1 } };
    return ret += min(x, y);
}
int main() {
    memset(dp, -1, sizeof(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(0, 0, 0));
    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;
}