洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

先整一个半成品，高精度过两天复习一下补上

#include <iostream>
#include <algorithm>
#include <set>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>#define endl '\n'using namespace std;
using LL = long long;
using ULL = unsigned long long;
typedef pair<int,int> PII;const LL inf = 4e18;
const int INF = 1e9;const ULL base = 131;
const int N = 50 + 9;
const int mod = 1e6 + 7;int n;
LL w[N];
LL f[N][N];void solve()
{cin >> n;for (int i = 1;i <= n;i ++) cin >> w[i];for (int len = 3;len <= n;len ++)for (int i = 1;i + len - 1 <= n;i ++){int j = i + len - 1;f[i][j] = inf;for (int k = i + 1;k < j;k ++)f[i][j] = min(f[i][j],f[i][k] + f[k][j] + w[i] * w[k] * w[j]);}cout << f[1][n] << endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;// cin >> _;while(_--) solve();return 0;
}