Cod sursa(job #1650900)

Utilizator RadduFMI Dinu Radu Raddu Data 11 martie 2016 21:25:54
Problema Parantezare optima de matrici Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#define inf (1LL<<62)
using namespace std;
ifstream f("podm.in");
ofstream g("podm.out");
 int n,v[1005]; int a1[505],a2[505];
 long long dp[505][505];
int main()
{ int i,j,t,len,i1,i2;
    f>>n;
    for(i=1;i<=n+1;i++)
     f>>v[i];

    for(i=1;i<=n;i++)
     for(j=i+1;j<=n;j++)
      if (i!=j) dp[i][j]=inf;

    for(i=1;i<=n;i++)
    { a1[i]=v[i];
      a2[i]=v[i+1];
    }
    for(i=1;i<=n;i++)
     dp[i][i+1]=1LL*a1[i]*a2[i]*a2[i+1];



  for(len=3;len<=n;len++)
   for(i=1;i<=n-len+1;i++)
    { i1=i; i2=i+len-1;
       for(t=i1;t<i2;t++)
        dp[i1][i2]=min(dp[i1][i2],dp[i1][t]+dp[t+1][i2]+1LL*a1[i1]*a2[t]*a2[i2]);
    }


   g<<dp[1][n];
    return 0;
}