#include<string>#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<cctype>
#include<cassert>
#include<vector>
#include <math.h>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;
const int inf=~0U>>1;
typedef long long ll;
int M[10][10];
int dp[10][10];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
cin>>dp[i][j];
}
}
for(int i=1;i<=n-1;i++)
dp[i][i]=0;
int j;
for(int r=2;r<=n;r++)
{
for(int i=1;i<=n+1-r;i++)
{
j=i+r-1;
for(int k=i+1;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
游艇租借
原文：http://www.cnblogs.com/vector11248/p/5018344.html
