C 解法, 执行用时: 3ms, 内存消耗: 332KB, 提交时间: 2022-06-21
#include <stdio.h>
#include <stdbool.h>
void printPreOrder(int start, int end, int **select) {
static bool isFirstPrint = true;
if (start <= end) {
int v = select[start][end];
if (isFirstPrint) {
printf("%d", v);
isFirstPrint = false;
} else {
printf(" %d", v);
}
printPreOrder(start, v-1, select);
printPreOrder(v+1, end, select);
}
}
int main() {
int n;
scanf("%d", &n);
int nums[n];
for(int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}
int **dp = (int **)malloc(sizeof(int *) * (n + 1));
int **select = (int **)malloc(sizeof(int *) * (n + 1));
for (int i = 0; i < n + 1; i++) {
dp[i] = (int *)malloc(sizeof(int) * (n + 1));
select[i] = (int *)malloc(sizeof(int) * (n + 1));
dp[i][i] = nums[i-1];
select[i][i] = i;
}
int maxDp, maxDpIndex, left, right, total;
for (int d = 1; d < n; d++) {
for (int i = 1; i <= n - d; i++) {
maxDp = 0;
maxDpIndex = 0;
for (int k = i; k <= i + d; k++) {
if (k == i) {
left = 1;
} else {
left = dp[i][k-1];
}
if (k == i + d) {
right = 1;
} else {
right = dp[k+1][i+d];
}
total = nums[k-1] + left * right;
if (total > maxDp) {
maxDp = total;
maxDpIndex = k;
}
}
dp[i][i+d] = maxDp;
select[i][i+d] = maxDpIndex;
}
}
printf("%d\n", dp[1][n]);
printPreOrder(1, n, select);
for (int i = 0; i < n + 1; i++) {
free(dp[i]);
free(select[i]);
}
free(dp);
free(select);
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-05-13
#include<bits/stdc++.h>
using namespace std;
int b[33][33];
int a[33];
int n;
void dfs(int i, int j){
if(i>j){
return;
}
cout<<b[i][j]<<" ";
dfs(i, b[i][j]-1);
dfs(b[i][j]+1, j);
}
int main(){
while(cin>>n){
for(int i=1;i<=n;i++){
cin>>a[i];
}
int dp[n+1][n+1];
memset(dp,0,sizeof(dp));
memset(b,0,sizeof(b));
for(int len=1;len<=n;len++){
for(int i=1;i<=n;i++){
int j=i+len-1;
if(j>n){
break;
}
if(len==1){
dp[i][j]=a[i];
b[i][j]=i;
}else{
for(int k=i;k<=j;k++){
int left= k==i?1:dp[i][k-1];
int right= k==j?1:dp[k+1][j];
int score=left*right+a[k];
if(score>dp[i][j]){
dp[i][j]=score;
b[i][j]=k;
}
}
}
}
}
cout<<dp[1][n]<<endl;
dfs(1,n);
}
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-06-06
#include<bits/stdc++.h>
using namespace std;
void print_root(int l, int r, vector<vector<int>> &record){
if (l > r) return;
cout<< record[l][r]+1<<" ";
print_root(l, record[l][r] - 1 , record);
print_root(record[l][r] + 1, r, record);
}
int main(){
int n;
cin >>n;
vector<int> v(n);
vector<vector<int>> dp(n,vector<int> (n));
vector<vector<int>> record(n, vector<int>(n));
for(int i = 0; i < n; ++i){
cin>> v[i];
dp[i][i] = v[i];//对于单节点区间中的积分值就是其自己
record[i][i] = i;//对于单节点区间中的root亦是其自己
}
for(int len = 2; len <= n; ++len){
int mx_l, mx_r,mx_root;
for(int l = 0; l < n; ++l){
int r = l + len - 1;
if(r >= n) break;
for(int root = l; root <= r; ++root){
int tmp = (root-1 < l ? 1: dp[l][root-1]) * (root+1 > r? 1: dp[root+1][r]) + v[root];
if(tmp > dp[l][r]) {
dp[l][r] = tmp;
record[l][r] = root;
}
}
}
}
cout<<dp[0][n-1]<<endl;
print_root(0,n-1,record);
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-03-26
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
void printdfs(vector<int>& tree,vector<vector<int>>& root,int s,int e) {
if (s == e) {
cout << s + 1 << " ";
return;
}
if (s > e) {
return;
}
cout << root[s][e] + 1 << " ";
printdfs(tree,root,s,root[s][e] - 1);
printdfs(tree,root,root[s][e] + 1,e);
}
int main() {
int n;
cin >> n;
vector<int> tree(n);
for (int i = 0; i < n; ++i) {
cin >> tree[i];
}
int ans = 0;
vector<vector<int>> dp(n,vector<int> (n));
vector<vector<int>> root(n,vector<int> (n));
for (int l = 0; l < n; ++l) {
for (int i = 0; i < n - l; ++i) {
int j = i + l;
//int tmax = 0;
int sum = 0;
for (int k = i; k <= j; ++k) {
//sum = tree[i];
sum = max (sum,tree[k]);
if (k - 1 >= i && tree[k] + dp[i][k - 1] > sum) {
sum = tree[k] + dp[i][k - 1];
root[i][j] = k;
}
if (k + 1 <= j && tree[k] + dp[k + 1][j] > sum) {
sum = tree[k] + dp[k + 1][j];
root[i][j] = k;
}
if (k - 1 >= i && k + 1 <= j && tree[k] + dp[k + 1][j] * dp[i][k - 1] > sum) {
sum = tree[k] + dp[k + 1][j] * dp[i][k - 1];
root[i][j] = k;
}
}
dp[i][j] = sum;
}
}
cout << dp[0][n - 1] << endl;
printdfs(tree,root,0,n - 1);
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-06-28
#include <iostream>
#include <vector>
using namespace std;
void printPath(vector<vector<int>>& dpc,int beginn,int endn)
{
int choose = dpc[beginn][endn];
cout << choose+1 << " ";
if(beginn < choose)
{
printPath(dpc,beginn,choose-1);
}
if(endn > choose)
{
printPath(dpc,choose+1,endn);
}
}
int main()
{
vector<int> list;
int n;
cin >> n;
for(int i = 0;i < n;i++)
{
int temp;
cin >> temp;
list.push_back(temp);
}
vector<vector<int>> dp(n,vector<int>(n,0));
vector<vector<int>> dpc(n,vector<int>(n,-1));
for(int i = 0;i < n;i++)
{
dp[i][i] = list[i];
dpc[i][i] = i;
}
for(int len = 1;len < n;len++)
{
for(int i = 0;i<n;i++)
{
if(i + len < n)
{
for(int j = i;j<=i+len;j++)
{
int comp = dp[i][i+len];
if(j == i)
{
dp[i][i+len] = max(dp[i][i+len],dp[j+1][i+len] + list[j]);
}
else if(j == i + len)
{
dp[i][i+len] = max(dp[i][i+len],dp[i][j-1] + list[j]);
}
else
{
dp[i][i+len] = max(dp[i][i+len],dp[i][j-1]*dp[j+1][i+len] + list[j]);
}
if(dp[i][i+len] > comp)
{
dpc[i][i+len] = j;
}
}
}
}
}
cout << dp[0][n-1] << endl;
printPath(dpc,0,n-1);
return 0;
}
，每个节点的值满足 