Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2017
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define i64 long long
  5. #define u32 unsigned int
  6. #define u64 unsigned long long
  7.  
  8. #define Neg(v) memset((v), -1, sizeof(v))
  9. #define Zero(v) memset((v), 0, sizeof(v))
  10.  
  11. #define ff first
  12. #define ss second
  13. #define sqr(x) ((x)*(x))
  14. #define INF LONG_LONG_MAX
  15. #define PI 2*acos(0)
  16. #define pb push_back
  17. #define ran(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a))
  18.  
  19. #define FLASH ios_base::sync_with_stdio(0);
  20.  
  21. const double eps = 1e-9;
  22. //int r[]={1,0,-1,0};int c[]={0,1,0,-1}; ///4 Direction
  23. //int r[]={1,1,0,-1,-1,-1,0,1};int c[]={0,1,1,1,0,-1,-1,-1};///8 direction
  24. //int r[]={2,1,-1,-2,-2,-1,1,2};int c[]={1,2,2,1,-1,-2,-2,-1};///Knight Direction
  25. //int r[]={2,1,-1,-2,-1,1};int c[]={0,1,1,0,-1,-1}; ///Hexagonal Direction
  26.  
  27. #define BIT(n) (1<<(n))
  28. #define AND(a,b) ((a) & (b))
  29. #define OR(a,b) ((a) | (b))
  30. #define XOR(a,b) ((a) ^ (b))
  31.  
  32. #define Check(n, pos) (n & (1<<pos))
  33. #define Set(n, pos) (n | (1<<pos))
  34.  
  35. int Unset(int a, int i)
  36. {
  37. int mask;
  38. mask = 1 << i;
  39. a = a & ~mask;
  40.  
  41. return a;
  42. }
  43.  
  44. template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % (b))); }
  45. template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b)) * (b)); }
  46. template <typename T> string NumberToString ( T Number ) { ostringstream ss; ss << Number; return ss.str(); }
  47.  
  48. int power( int x, int n)
  49. {
  50. if(n==0)return 1;
  51. else if(n%2==0)
  52. {
  53. int y=power(x,n/2);
  54. return y*y;
  55. }
  56. else
  57. return x*power(x,n-1);
  58. }
  59.  
  60. /// Tokens
  61.  
  62. /*
  63. vector <int> lon;
  64. vector <string> los;
  65.  
  66. void token_of_string()
  67. {
  68. char line[1000];
  69. gets(line);
  70. stringstream ss( line );
  71. string temp;
  72. while( ss >> temp )
  73. los.pb( temp );
  74. }
  75.  
  76. void token_of_number()
  77. {
  78. char line[1000];
  79. gets(line);
  80. stringstream ss( line );
  81. int num;
  82. while( ss >> num )
  83. lon.pb( num );
  84. }
  85.  
  86. */
  87.  
  88.  
  89. ///1st,2nd,3rd
  90.  
  91. /*
  92. void func( int num )
  93. {
  94. printf("%d",num);
  95. if(num % 10 == 1 && (num/10)%10!=1) printf("st");
  96. else if(num %10==2 && (num/10)%10!=1) printf("nd");
  97. else if(num %10==3 && (num/10)%10!=1) printf("rd");
  98. else printf("th");
  99. }
  100. */
  101.  
  102.  
  103.  
  104. /***
  105.  
  106. int nth_element( int a , int d , int n)
  107. {
  108. return a + (n-1) * d;
  109. }
  110.  
  111. int nth_summation( int a , int d , int n)
  112. {
  113. int temp;
  114. temp = 2 * a + (n-1)*d;
  115. temp *= n;
  116. temp /= 2;
  117.  
  118. return temp;
  119. }
  120.  
  121. ***/
  122.  
  123.  
  124. /***
  125. n row ; m collumn
  126. 2d in 1d
  127. int x = A / m , y = A % m;
  128. visited[0][x] = 1, visited[1][y] = 1,visited[2][x+y] = 1,visited[3][n-x+y] = 1;
  129. ***/
  130.  
  131. #ifdef blackfyre
  132. #define debug(args...) {cerr<<"Debug: "; dbg,args; cerr<<endl;}
  133. #else
  134. #define debug(args...) // Just strip off all debug tokens
  135. #endif
  136.  
  137. struct debugger{
  138. template<typename T> debugger& operator , (const T& v){
  139. cerr<<v<<" ";
  140. return *this;
  141. }
  142. }dbg;
  143.  
  144.  
  145. struct data
  146. {
  147. string x ;
  148.  
  149. double a , b ;
  150. };
  151.  
  152. data v1[510];
  153. int n ;
  154.  
  155. int visited[510][2][5] ;
  156. double dp[510][2][5] ;
  157.  
  158. double call( int pos , bool st , int c1 )
  159. {
  160.  
  161. if( pos >= n )
  162. {
  163. if( st && c1 == 4 )
  164. return 0.0;
  165. else
  166. return 9999 ;
  167. }
  168.  
  169.  
  170. if( visited[pos][st][c1] != -1 )
  171. return dp[pos][st][c1] ;
  172.  
  173. visited[pos][st][c1] = 1 ;
  174.  
  175. double option1 = 99999.0, option2 = 99999.0, option3 = 99999.0;
  176.  
  177. if(!st)
  178. option1 = v1[pos].a + call(pos+1,1,c1+1);
  179.  
  180. option2 = v1[pos].b + call(pos+1,st,c1+1);
  181.  
  182. option3 = call(pos+1,st,c1);
  183.  
  184.  
  185. return dp[pos][st][c1] = min( option1 , min(option2 , option3 ) ) ;
  186.  
  187. }
  188.  
  189.  
  190.  
  191. int main()
  192. {
  193. #ifdef blackfyre
  194.  
  195. //freopen("F:/in.txt","r",stdin);
  196. //freopen("F:/out.txt","w",stdout);
  197.  
  198. #endif // blackfyre
  199.  
  200.  
  201.  
  202. while( cin >> n )
  203. {
  204.  
  205. Neg(visited);
  206. cin.ignore();
  207. for( int A = 0 ; A < n ; A++ )
  208. {
  209. cin >> v1[A].x ;
  210. cin >> v1[A].a ;
  211. cin >> v1[A].b ;
  212. }
  213.  
  214.  
  215.  
  216. double ans = call(0,0,0) ;
  217.  
  218.  
  219.  
  220. }
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement