codeforces 580D Kefa and Dishes [상태 압축 + dp]

4361 단어 dp
제목 대의: n개 요리 중 m개 요리를 골라 먹으면 매 요리마다 만족도ai가 있고 그 밖에 k가지 상황이 있다. 먼저 xi를 먹고 yi를 먹으면 추가적으로ci만족도를 증가시킨다.최대 만족도를 묻다.
사고방식: 수조 dp[1<#include #include #include #include using namespace std; typedef __int64 LL; const int MAXN = 20; LL sat[MAXN]; LL map[MAXN][MAXN]; LL dp[1<1<int n, int m) { memset(dp, -1, sizeof(dp)); memset(num, 0, sizeof(num)); LL ans = 0; for(int i = 0; i < n; i++) { dp[1<1<1; if(m == 1) ans = max(ans, sat[i]); } int t = 1 << n; for(int i = 0; i < t; i++) for(int j = 0; j < n; j++) if(i&(1<int u = i - (1 << j); for(int k = 0; k < n; k++) if(dp[u][k] != -1) { dp[i][j] = max(dp[i][j], dp[u][k] + map[k][j] + sat[j]); num[i] = num[u] + 1; } if(num[i] == m) ans = max(dp[i][j], ans); } return ans; } int main(int argc, char const *argv[]) { int n, m, k; cin >> n >> m >> k; for(int i = 0; i < n; i++) cin >> sat[i]; memset(map, 0, sizeof(map)); while(k--) { int x, y; LL c; cin >> x >> y >> c; map[x-1][y-1] = c; } cout << sol(n, m) << endl; return 0; }

좋은 웹페이지 즐겨찾기