[UVa] 12836 - Gain Battle Power

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12836 - Gain Battle Power
Source            : CodeChef
Category          : Dynamic Programing Optimization
Algorithm         : Knuth Optimization
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define ll         long long int  
  
static const int maxn = 1000 + 5;  
  
int n;  
int strength[maxn];  
ll power[maxn], sumPower[maxn];  
int Right[maxn], Left[maxn];  
  
inline int goRight(int u)   // LDS in right part  
{  
      if (Right[u] != -1) return Right[u];  
      int maxi = 0;  
      for (int v = u+1; v <= n; v++)  
      {  
            if (strength[v] < strength[u])  
            {  
                  if (goRight(v) > maxi)  
                  {  
                        maxi = goRight(v);  
                  }  
            }  
      }  
      Right[u] = 1 + maxi;  
      return Right[u];  
}  
  
inline int goLeft(int u) // LDS in left part  
{  
      if (Left[u] != -1) return Left[u];  
      int maxi = 0;  
      for (int v = u-1; v >= 1; v--)  
      {  
            if (strength[v] < strength[u])  
            {  
                  if (goLeft(v) > maxi)  
                  {  
                        maxi = goLeft(v);  
                  }  
            }  
      }  
      Left[u] = 1 + maxi;  
      return Left[u];  
}  
  
inline void Power()  
{  
      for (int i = 1; i <= n; i++)  
      {  
            power[i] = Right[i] + Left[i] - 1;  
            sumPower[i] = sumPower[i-1] + power[i];  
      }  
}  
  
inline ll getPower(int l, int r)  
{  
    return sumPower[r] - sumPower[l];  
}  
  
ll dp[maxn][maxn];  
bool vis[maxn][maxn];  
int mid[maxn][maxn];  
  
/**           TLE 
ll solve(int left, int right) 
{ 
      if (left == right) return 0; 
      ll &ret = dp[left][right]; 
      bool &v = vis[left][right]; 
      if (v == 1) return ret; 
      v = 1; 
      ll mini = 1e17 + 7; 
      for (int i = left; i < right; i++) 
      {  
          ll temp = solve(left, i) + solve(i+1, right) + getPower(left, right); 
          if (temp < mini) mini = temp; 
      } 
      return ret = mini; 
} 
**/  
  
inline ll knuth_optimization()  
{  
      memset(dp, 0, sizeof dp);  
      memset(mid, 0, sizeof mid);  
      for (int s = 0; s <= n; s++)  
      {  
          for (int l = 0; l+s <= n; l++)  
          {  
              int r = l+s;  
              if (s < 2)  
              {  
                  dp[l][r] = 0;  
                  mid[l][r] = l;  
                  continue;  
              }  
              int mleft = mid[l][r-1];  
              int mright = mid[l+1][r];  
              dp[l][r] = 1e17 + 7;  
              for (int mm = mleft; mm <= mright; mm++)  
              {  
                  ll tmp = dp[l][mm] + dp[mm][r] + getPower(l, r);  
                  if (tmp < dp[l][r])  
                  {  
                      dp[l][r] = tmp;  
                      mid[l][r] = mm;  
                  }  
              }  
          }  
      }  
      return dp[0][n];  
}  
  
inline void init()  
{  
      memset(strength, 0, sizeof strength);  
      memset(vis, 0, sizeof vis);  
      memset(Right, -1, sizeof Right);  
      memset(Left, -1, sizeof Left);  
}  
  
int main()  
{  
      int tc;  
      scanf("%d", &tc);  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            init();  
            scanf("%d", &n);  
            for (int i = 1; i <= n; i++) scanf("%d", strength+i);  
            for (int i = 1; i <= n; i++) goRight(i);  
            for (int i = n; i >= 1; i--) goLeft(i);  
            Power();  
            //ll ans = solve(1, n);  
            ll ans = knuth_optimization();  
            printf("Case %d: %lld\n", tcase, ans);  
      }  
}