NYoj536 矩阵链乘

经典问题没啥说的

#include<stdio.h>

#include<string.h>
#define max 100+1
#define min(a,b) (a<b?a:b)
typedef long long LL;
LL dp[max][max];
int p[max];

int main(){
   int n;
   while(~scanf("%d",&n)){
       int i,j,k,l;
       for(i=1;i<=n;i++){
           scanf("%d%d",&p[i-1],&p[i]);
           dp[i][i]=0;
       }
       for(l=2;l<=n;l++){
           for(i=1;i+l-1<=n;i++){
               j=i+l-1;
               LL& tmp=dp[i][j];
               tmp=999999999;
               for(k=i;k<j;k++){
                   tmp=min(dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j],tmp);
               }
           }
       }
       printf("%lld\n",dp[1][n]);
   }
}

巴特西

NYoj536 矩阵链乘

最新文章

热门文章