洛谷过了,青藤没过,发现洛谷有SPJ,青藤没有。。
https://www.luogu.com.cn/record/124974537
#include <bits/stdc++.h>
using namespace std;
int arr[105];
int dp[105][105], rt[105][105];
void prt(int l, int r) {
cout << rt[l][r] << " ";
if (l <= rt[l][r] - 1) {
prt(l, rt[l][r] - 1);
}
if (rt[l][r] + 1 <= r) {
prt(rt[l][r] + 1, r);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i][j] = 1;
}
}
for (int i = 1; i <= n; i++) {
cin >> arr[i];
dp[i][i] = arr[i];
rt[i][i] = i;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
if (dp[i][j] < dp[i][k - 1]*dp[k + 1][j] + arr[k]) {
dp[i][j] = dp[i][k - 1] * dp[k + 1][j] + arr[k];
rt[i][j] = k;
}
}
}
}
cout << dp[1][n] << endl;
prt(1, n);
}
共 2 条回复
@cookiebus
@cookiebus