ulvis.paste.net

Paste Search Dynamic
solve
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define MAX 22
  5.  
  6. const ll mod = 1000000007;
  7. ll n, k, tot, adj[MAX][MAX], dp[MAX][(1LL<<20)], par[MAX];
  8.  
  9. ll solve(ll id, ll mask) {
  10.         if(id == n + 1) {
  11.                 if(mask == tot) {
  12.                         return 0;
  13.                 }
  14.                 return mod;
  15.         }
  16.         if(dp[id][mask] != -1) {
  17.                 return dp[id][mask];
  18.         }
  19.         ll mn = solve(id + 1, mask);
  20.         par[id] = -1;
  21.         for(int i = 1; i <= k; i++) {
  22.                 if(!(mask&(1LL << i))) {
  23.                         ll nmask = mask|(1LL << i);
  24.                         ll nval = adj[i][id] + solve(id + 1, nmask);
  25.                         if(mn > nval) {
  26.                                 mn = nval;
  27.                                 par[id] = i;
  28.                         }
  29.                 }
  30.         }
  31.         return dp[id][mask] = mn;
  32. }
  33.  
  34. int main() {
  35.         ll k, n;
  36.         cin >> k >> n;
  37.         for(int i = 1; i <= k; i++) {
  38.                 for(int j = 1; j <= n; j++) {
  39.                         cin >> adj[i][j];
  40.                 }
  41.         }
  42.         tot = (1LL << (k + 1)) - 2;
  43.  
  44.         cout << solve(1, 0) << endl;
  45.  
  46.         return 0;
  47. }
Parsed in 0.006 seconds