kburnik

C++ - Zadatak Kule (rješenje)

Mar 1st, 2013
59
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Zadatak: Kule
  3.              http://bit.ly/zadatak-kule
  4.    
  5.     Složenost: << faktorijelna zbog memoizacije!
  6.  
  7.     Datum: 2013-03-01
  8.  
  9.     Autor: Goran Žužić, HSIN
  10.    
  11.     Ponuđeno rješenje: Kristijan Burnik, udruga informatičara Božo Težak
  12.  
  13.     Gmail: kristijanburnik
  14. */
  15. #include <iostream>
  16. #include <cstdlib>
  17. #include <cmath>
  18.  
  19. using namespace std;
  20.  
  21. int n;
  22. int a[20][20];
  23. int sums[0x100000] = {0};
  24.  
  25. int maxsuma(int free,int size) {
  26.  
  27.    int saved = sums[free];
  28.    if (saved > 0) return saved;
  29.    
  30.    if (size == 2) {
  31.         int r[2] = {n-2,n-1};
  32.         int c[2] = {0,0};    
  33.         int cc = 0;
  34.         int bits = free;
  35.        
  36.         for (int i = 0; i < n && cc<2; i++) {          
  37.             if (bits & 1) {
  38.                 c[cc] = i;
  39.                 cc++;
  40.             }
  41.             bits >>= 1;
  42.         }
  43.  
  44.         return (
  45.             sums[free] = max (
  46.                         a[ r[0] ][ c[0] ] + a[ r[1] ][ c[1] ] ,
  47.                         a[ r[1] ][ c[0] ] + a[ r[0] ][ c[1] ]
  48.                     )
  49.         );
  50.    }
  51.  
  52.    int r = n - size;
  53.    int max = 0;
  54.    int bits = free;
  55.    int onecount = 0;
  56.    
  57.    for (int i = 0; i < n && onecount < size; i++) {
  58.         if (bits & 1) {
  59.             int suma = a[r][i] +  maxsuma(free - (1 << i), size - 1);
  60.             if (suma > max) max = suma;
  61.             onecount++;
  62.         }
  63.         bits >>= 1;
  64.     }
  65.    
  66.     return sums[free] = max ;
  67. }
  68.  
  69. int main(void) {
  70.  
  71.     cin >> n;    
  72.     for (int i = 0 ; i < n; i++)
  73.         for (int j = 0 ; j < n; j++)
  74.             cin >> a[i][j];
  75.  
  76.     int free = (1 << n) - 1;    
  77.     cout << maxsuma(free,n) << endl;
  78.    
  79.     return 0;
  80. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×