[BAE/<JOON> 문제풀이] 1029. 그림 교환

https://www.acmicpc.net/problem/1029

1029번: 그림 교환

서론

상류층들의 취미용 재테크 미술품 되팔이 ㄷㄷㄷㄷ

그냥 DFS DP 인데 난이도에 비해 티어가 너무 높은 느낌이다. TSP 문제들은 티어 좀 까야하지 않나 싶다.

풀이

단순 DP + DFS 방문이라 딱히 쓸게 없다.

DP 배열은 아래와 같다.

• DP[i][j][k] = i 번째 예술가가 j의 가격으로 k 상태의 방문 배열에서 얻을 수 판매 횟수

점화식은 아래와 같다.

• DP[i][j][k] = i 번째 예술가가  판매할 예술가들의 판매 횟수 중 가장 많은 판매 횟수 + 1

현재 방문 가능한 예술가들을 DFS 탐색하며 가장 많은 판매 횟수를 올린 예술가를 찾으면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
using ull = long long;
struct dk {
    ull i, v;
};
struct cmp {
    bool operator()(dk a, dk b) {
        return a.v < b.v;
    }
};
int n; int mx = 0;
vector<int> ch; vector<vector<int>> arr; vector<vector<vector<int>>> dp;
int dfs(int cur, int v, int stat) {
    int& ret = dp[cur][v][stat];
    if (ret != -1) return ret;
    int m = 0;
    for (int i = 1; i <= n; i++) {
        if (ch[i] == 0 && v <= arr[cur][i]) {
            ch[i] = 1;
            int ret = dfs(i, arr[cur][i], stat | (1 << (i - 1)));
            m = ret > m ? ret : m;
            ch[i] = 0;
        }
    }
    return ret = m + 1;
}
int main() {
    cin >> n; arr.resize(n + 1, vector<int>(n + 1)); ch.resize(n + 1, 0); dp.resize(n + 1, vector<vector<int>>(10, vector<int>((1 << n), -1)));
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        for (int j = 1; j <= n; j++) {
            arr[i][j] = s[j - 1] - 48;
        }
    }
    ch[1] = 1;
    cout << dfs(1, 0, 1);
    return 0;
}