fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int dx[1005][1005];
  4. int dy[1005][1005];
  5. long long int dp[1005][1005];
  6. int h[10005];
  7. long long int f(int v[],int x,int y,int n,int level)
  8. {
  9.  
  10.     if(x < 1 || y > n) {
  11.         return LONG_MAX;
  12.     }
  13.  
  14.     if(level == n) {
  15.         return n;
  16.     }
  17.     if(dp[x][y] != 0) {
  18.         return dp[x][y];
  19.     }
  20.  
  21.      long long int left = f(v,min(x,y)-1,y,n,level+1) + ((long long)level*(long long)dx[x][y]);
  22.     //cout<<h[x]<<' '<<h[y]<<endl;
  23.     //cout<<level<<' '<<dx[x][y]<<endl;
  24.      long long int right = f(v,x,max(x,y)+1,n,level+1) + ((long long)level*(long long)dy[y][x]);
  25.    // cout<<x<<' '<<y<<endl;
  26.    // cout<<level<<' '<<left<<' '<<right<<endl;
  27.     dp[x][y] =  min(left,right);
  28.     return dp[x][y];
  29.  
  30.  
  31. }
  32. int main()
  33. {
  34.     int n;
  35.     int t;
  36.     int i;
  37.     long long int x;
  38.     long long int min;
  39.     int j;
  40.     int a[100005];
  41.  
  42.  
  43.     cin>>t;
  44.     while(t--) {
  45.         scanf("%d",&n);
  46.         //n = 1000;
  47.         memset(dp,0,sizeof(dp));
  48.         min = LONG_MAX;
  49.         for(i = 0; i < n; i++) {
  50.             scanf("%d",&a[i]);
  51.             h[a[i]] = i+1;
  52.         }
  53.         for(i = 1; i <= n; i++) {
  54.             dx[i][i] = h[i];
  55.             for(j = i+1; j <= n; j++) {
  56.                 dx[i][j] = dx[i][j-1] - (h[i]>h[j]?1:0);
  57.             }
  58.         }
  59.         for(i = 1; i <= n; i++) {
  60.             dy[i][i] = h[i];
  61.             for(j = i-1; j >= 1; j--) {
  62.                 dy[i][j] = dy[i][j+1] - (h[i]>h[j]?1:0);
  63.             }
  64.  
  65.         }
  66.         for(i = 0; i < n; i++) {
  67.             x = f(a,a[i],a[i],n,1);
  68.          //   cout<<x<<" ss"<<endl;
  69.             //cout<<"ss"<<endl;
  70.             if(x < min) {
  71.                 min = x;
  72.             }
  73.         }
  74.         printf("%lld\n",min);
  75.     }
  76. }
  77.  
Success #stdin #stdout 0s 19232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uApUv1
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!