TIOJ 1388 好強的史來姆 [DP]

poao899    28K    906MS    G++     0.52K     2009-11-18 09:09:04                                 .


跟正直DE(矩陣乘法最小花費)一樣類型

不過卡得頗緊|||


O(n^3)但是得壓常數Q


//***********************

//1388

#include<stdio.h>
long long dp[100][100];
int slime[100],n;
main(){
 while(~scanf("%d",&n)){
  for(int i=0;i<n;i++){
   scanf("%d",slime+i);
   for(int j=0;j<n;j++)
    dp[i][j]=i==j?slime[i]:0;
  }
  for(int j=2;j<=n;j++)
   for(int i=0;i+j<=n;i++){
    int z=i+j-1;
    for(int k=i;k<z;k++){
     dp[i][z]>?=(j&1)?dp[i][k]*dp[k+1][z]:dp[i][k]+dp[k+1][z];
    }
   }
  printf("%I64d\n",dp[0][n-1]);
 }
}