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

SmallY

记忆化搜索.算法导论P210例题

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])
Andrew-Malcom
#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;
    }
}
CCXXXI_

再次推荐functools.lru_cache,写DP的时候用来做记忆化搜索真的超好用

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

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

include

include

include

include

include

include

include

include

define REP(i,n) for(int i=0;i<(n);++i)

define FOR(i,a,b) for (int i=a;i<=b;i++)

define mem(a) memset(a,0,sizeof(a))

define db(x) cout << x << endl

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

Fifnmar

我的思路和其他各位差不多,但我是从 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).
$$

其中,$a(i)$ 是 $i$ 号矩阵的行数,$a(i + 1)$ 是 $i$ 号矩阵的列数。

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';
    }
}
10175102262 LarsPendragon

动态规划。相信oj,直接循环就可以AC,完全不用优化代码。
思路:dp[i][j]表示从第i个矩阵到第j个矩阵的最小乘法次数,则结果只需输出dp[1][n]即可。用num[x]存储矩阵大小。
显然,当i=j时dp[i][j]=0(因为不需要计算乘法),而当i < j时,可能出现j-i种情况,其中“断点”设为k,则dp[i][j]=min(dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j])
附C代码:

#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;
}
你当前正在回复 博客/题目
存在问题!