前言
__int128 yyds!!!
还有初始值不能设的过大,我本来设了 $999999999999999999999999$,结果连 __int128 都爆了,WA 了一次
时间复杂度
$O(N^3)$
空间复杂度
$O(N^2)$
c++
代码
# include <bits/stdc++.h>
# define old_six \
ios::sync_with_stdio (0);\
\
cin.tie (0);\
\
cout.tie (0);
# define ffor(i,name) \
for (auto i = name.begin (); i != name.end (); i ++)
# define iter(type) \
type :: iterator
# define reg register
# define inl inline
//# define int __int128
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
int n, a[55];
__int128 dp[55][55];
string ans;
int main () {
old_six
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
for (int len = 2; len < n; ++ len)
for (int l = 1, r; (r = l + len) <= n; ++ l) {
dp[l][r] = (__int128) (LLONG_MAX - 1) * (LLONG_MAX - 1);
for (int k = l + 1; k < r; ++ k)
dp[l][r] = min (dp[l][r], dp[l][k] + dp[k][r] + (__int128) a[l] * a[k] * a[r]);
}
// cout << dp[1][n] << '\n';
while (dp[1][n])
ans = (char) (dp[1][n] % 10 + '0') + ans, dp[1][n] /= 10;
cout << ans;
return 0;
}