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])

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())

#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;
    }
}

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;
}