# 1051. 完全加括号的矩阵连乘积

def search(p, i, j):
global res
if i == j:
return 0
if res[i][j] < 0xfffffffff:
return res[i][j]
for k in range(i, j):
q = search(p, i, k)+search(p, k+1, j)+p[i]*p[k+1]*p[j+1]
if q < res[i][j]:
res[i][j] = q
return res[i][j]

N = int(input())
for i in range(N):
n = int(input())
res = [[0xfffffffff]*(n) for i in range(n)]
p = []
x, y = map(int, input().split())
p.append(x)
p.append(y)
for i in range(1, n):
x, y = map(int, input().split())
p.append(y)
search(p, 0, n-1)
print(res[0][n-1])
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f;
int main()
{
int t;cin>>t;
while(t--){
ll dp[101][101];
memset(dp,INF,sizeof(dp));
int n;cin>>n;
struct Node{int x,y;}stu[n];
for(int i=0;i<n;i++) cin>>stu[i].x>>stu[i].y;
for(int i=0;i<n;i++) dp[i][i]=0;
for(int len=1;len<n;len++){
for(int i=0;i+len<n;i++){
int j=i+len;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+stu[i].x*stu[k].y*stu[j].y);
}
}
}
cout<<dp[0][n-1]<<endl;
}
}

from functools import lru_cache as lc

for _ in range(int(input())):
n = int(input())
x = list(map(int, input().split() + [input().split()[1] for _ in range(n - 1)]))

@lc(None)
def f(i=0, j=n-1):
return 0 if i == j else min(f(i, k) + x[i] * x[k + 1] * x[j + 1] + f(k + 1, j) for k in range(i, j))

print(f())

INF开太小WA了两次,做法就是动态规划

### define dbb(x,y) cout << x << ” ” << y << endl

using namespace std;
typedef long long ll;
int n,T;
ll f[60][60];
ll a[60],b[60];
const ll inf =4611686018427387904;
ll solve(int l, int r) {
if (f[l][r] != -1) return f[l][r];
if (l == r - 1) return f[l][r] = a[l] * b[l] * b[r];
if (l == r) return f[l][r] = 0;
long long ans = inf;
for (int x = l ; x < r; x++){
ans = min(ans, solve(l, x) + solve(x+1, r) + a[l] * b[x] * b[r]);
}
return f[l][r] = ans;
}

int main() {
scanf(“%d”, &T);
while (T–) {
cin >> n;
REP(i,n)
cin >> a[i] >> b[i];
memset(f, 0xff, sizeof(f));
cout << solve(0,n-1)<<endl;
}
return 0;
}

$$dp(i, j) = \min (dp(i, k - 1) + dp(k, j) + c * a(k)), k \in (i, j], c = a(i) * a(j + 1).$$

int main() {
u32 t, n; cin >> t;
for (u32 i = 0; i < t; ++i) {
cin >> n;
vector<u64> a(n + 1);
cin >> a[0] >> a[1];
for (u32 j = 2; j <= n; ++j) {
cin >> a[j] >> a[j];
}
vector dp(n, vector<u64>(n));
for (u32 j = 0; j < n; ++j) {
dp[j][j] = 0;
}
for (u32 s = 1; s < n; ++s) {
for (u32 i = 0, j = s; j < n; ++i, ++j) {
auto c = a[i] * a[j + 1];         // c is the coefficient "a[i] * a[j]". --Constant Optimization
auto d = dp[i][j - 1] + c * a[j]; // d is current max, initialized with k = j;
for (u32 k = i + 1; k < j; ++k)
if (auto t = dp[i][k - 1] + dp[k][j] + c * a[k]; d > t)
d = t;
dp[i][j] = s;
}
}
cout << dp[0][n - 1] << '\n';
}
}

#include <stdio.h>
int main()
{
int T, I;
scanf("%d",&T);
for(I=0; I<T; I++)
{
int n, i, num[51], t, j, k;
unsigned long long dp[51][51];
scanf("%d",&n);
scanf("%d %d",&num[0], &num[1]);
for(i=0; i<51; i++) for(j=0; j<51; j++) dp[i][j]=0-1;
dp[0][0]=0;
dp[1][1]=0;
for(i=1; i<n; i++)
{
scanf("%d %d",&t, &num[i+1]);
dp[i+1][i+1]=0;
}
for(i=1; i<=n; i++)
for(j=1; j<=n-i; j++)
for(k=j; k<j+i; k++)
dp[j][j+i]=dp[j][j+i]>dp[j][k]+dp[k+1][j+i]+num[j-1]*num[k]*num[j+i]?dp[j][k]+dp[k+1][j+i]+num[j-1]*num[k]*num[j+i]:dp[j][j+i];
printf("%llu\n",dp[1][n]);
}
return 0;
}