非高精度写法
数据范围小这个就可以过了
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int w[N];
int f[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
w[i + n] = 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] = 1e9;
for (int k = i + 1; k < j; k++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + w[i] * w[j] * w[k]);
}
}
}
cout<<f[1][n];
return 0;
}
高精度乘法+高精度加法
static LL c[M];
是为了每次调用 mul 或 add ,不用开辟新的c数组,节省空间
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 55, M = 35;
LL w[N];
LL f[N][N][M];
LL temp[M];
void mul(LL a[], LL b) {
static LL c[M];
memset(c, 0, sizeof c);
LL t = 0;
for (int i = 0; i < M; i++) {
t += a[i] * b;
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}
void add(LL a[], LL b[]) {
static LL c[M];
memset(c, 0, sizeof c);
for (int i = 0, t = 0; i < M; i++) {
t += a[i] + b[i];
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}
int cmp(LL a[], LL b[]) {
for (int i = M - 1; i >= 0; i--) {
if (a[i] != b[i])return a[i] > b[i] ? 1 : -1;
}
return 0;
}
void print(LL a[]) {
int k = M - 1;
while (k && !a[k])k--;
while (k >= 0)cout << a[k--];
cout << endl;
}
int main() {
freopen("data.txt", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
w[i + n] = 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][M - 1] = 1; // f[i][j]设为INF
for (int k = i + 1; k < j; k++) {
memset(temp, 0, sizeof temp);
temp[0] = w[i];
mul(temp, w[j]);
mul(temp, w[k]);
add(temp, f[i][k]);
add(temp, f[k][j]);
if (cmp(f[i][j], temp) > 0) {
memcpy(f[i][j], temp, sizeof temp);
}
// f[i][j] = min(f[i][j], f[i][k] + f[k][j] + w[i] * w[j] * w[k]);
}
}
}
print(f[1][n]);
return 0;
}
网友评论