NonWhite

spoj hist2

Oct 19th, 2012
433
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <sstream>
  3. #include <bitset>
  4. #include <cstdio>
  5. #include <string>
  6. #include <cstring>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <set>
  11. #include <map>
  12. #include <algorithm>
  13. #include <cmath>
  14. #include <cstdlib>
  15. #include <cctype>
  16. #include <numeric>
  17. #define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
  18. #define mp make_pair
  19. #define debug( x ) cout << #x << " = " << x << endl
  20. #define clr(v,x) memset( v, x , sizeof v )
  21. #define all(x) (x).begin() , (x).end()
  22. #define rall(x) (x).rbegin() , (x).rend()
  23. #define f(i,a,b) for(int i = a ; i < b ; i++)
  24. #define fd(i,a,b) for(int i = a ; i >= b ; i--)
  25. #define TAM 110
  26.  
  27. using namespace std;
  28.  
  29. typedef pair<int,int> ii ;
  30. typedef long long ll ;
  31. typedef long double ld ;
  32. typedef pair<int,ii> pii ;
  33.  
  34. ii dp[ 20 ][ 1<<20 ] ;
  35. int n ;
  36. int v[ TAM ] ;
  37.  
  38. ii calc( int x , int mask ){
  39.     ii & resp = dp[ x ][ mask ] ;
  40.     if( resp.first != -1 ) return resp ;
  41.  
  42.     if( mask == ((1<<n)-1) ) return mp( v[ x ] + n , 1 ) ;
  43.  
  44.     resp = mp( 0 , 1 ) ;
  45.     f( i , 1 , n +1 ){
  46.         if( mask & (1<<(i-1)) ) continue ;
  47.         ii aux = calc( i , mask | (1<<(i-1)) ) ;
  48.         aux.first += ( abs( v[ x ] - v[ i ] ) + 1 ) ;
  49.         if( aux.first > resp.first )
  50.             resp = aux ;
  51.         else if( aux.first == resp.first )
  52.             resp.second++ ;
  53.     }
  54.  
  55.     return resp ;
  56. }
  57.  
  58. int main(){
  59.  
  60.     while( scanf("%d" , &n ) == 1 ){
  61.         if( n == 0 ) break ;
  62.         f( i , 1 , n + 1 ) scanf("%d" , &v[ i ] ) ;
  63.         v[ 0 ] = 0 ;
  64.  
  65.         f( i , 0 , n + 1 ) f( j , 0 , 1<<n ) dp[ i ][ j ] = mp( -1 , -1 ) ;
  66.         ii R = calc( 0 , 0 ) ;
  67.         printf("%d %d\n" , R.first ,R.second ) ;
  68.     }
  69.     return 0 ;
  70. }
RAW Paste Data