fork download
copy 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26. #define SZ(x) ((vlong)(x).size())
  27. #define NORM(x) if(x>=mod)x-=mod;
  28.  
  29. using namespace std;
  30.  
  31. typedef long long vlong;
  32.  
  33. const vlong inf = 2147383647;
  34.  
  35. /***********Template Ends Here***********/
  36. int arr[1010];
  37.  
  38. vlong LIS[1010], LDS[1010], pwr[1010], cum[1010];
  39.  
  40. vlong memo[1010][1010];
  41. int knuth[1010][1010], cc = 1;
  42. int done[1010][1010];
  43.  
  44. vlong dp ( int st, int en ) {
  45.     if ( st == en ) {
  46.         knuth[st][en] = st;
  47.         return 0;
  48.     }
  49.     if ( done[st][en] == cc ) return memo[st][en];
  50.  
  51.     vlong res = inf * inf;
  52.  
  53.     dp ( st, en - 1 ); ///First calculate this
  54.     dp ( st + 1, en ); ///First calculate this
  55.  
  56.     int kst = knuth[st][en-1]; ///Knuth's Optimization
  57.     int ken = knuth[st+1][en]; ///Knuth's Optimization
  58.     if ( ken == en ) ken--;
  59.  
  60.     FOR ( iron, kst, ken ) {
  61.         vlong cost = cum[en] - cum[st-1];
  62.         vlong tres = cost + dp ( st, iron ) + dp ( iron + 1, en );
  63.         if ( tres <= res ) {
  64.             res = tres;
  65.             knuth[st][en] = iron;
  66.         }
  67.     }
  68.  
  69.     done[st][en] = cc;
  70.     return memo[st][en] = res;
  71. }
  72.  
  73.  
  74. int main () {
  75.     #ifdef forthright48
  76.     freopen ( "input.txt", "r", stdin );
  77.     //freopen ( "output.txt", "w", stdout );
  78.     #endif // forthright48
  79.  
  80.     int kase, cnt = 0;
  81.     scanf ( "%d", &kase );
  82.  
  83.     while ( kase-- ) {
  84.         int n;
  85.         scanf ( "%d", &n );
  86.  
  87.         FOR(iron,0,n-1){
  88.             scanf ( "%d", &arr[iron] );
  89.         }
  90.  
  91.         FOR(iron,0,n-1){
  92.             LIS[iron] = 1;
  93.             LDS[iron] = 1;
  94.         }
  95.  
  96.  
  97.         ///Find LIS from front
  98.         FOR(iron,0,n-1){
  99.             FOR(joker,iron+1,n-1){
  100.                 if ( arr[iron] < arr[joker] && LIS[iron] + 1 > LIS[joker] ) {
  101.                     LIS[joker] = LIS[iron] + 1;
  102.                 }
  103.             }
  104.         }
  105.         ///Find LIS from back
  106.         ROF(iron,0,n-1){
  107.             ROF(joker,0,iron-1){
  108.                 if ( arr[iron] < arr[joker] && LDS[iron] + 1 > LDS[joker] ) {
  109.                     LDS[joker] = LDS[iron] + 1;
  110.                 }
  111.             }
  112.         }
  113.  
  114.         ///Calculate PWR. Made it 1-indexed
  115.         FOR(iron,0,n-1){
  116.             pwr[iron+1] = LIS[iron] + LDS[iron] - 1;
  117.             cum[iron+1] = pwr[iron+1] + cum[iron];
  118.         }
  119.  
  120.         ///Now calculate DP
  121.         cc++;
  122.         vlong res = dp ( 1, n );
  123.  
  124.         printf ( "Case %d: %lld\n", ++cnt, res );
  125.     }
  126.  
  127.     return 0;
  128. }
  129.  
Time limit exceeded #stdin #stdout 5s 19432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XD6hZP
Blog UVa 12836 - Gain Battle Power
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!