【NOIP考前题目回顾】Luogu P1040

【NOIP考前题目回顾】Luogu P1040

思路

第一问看上去像是个树形结构，但是其实我们可以把它直接看成是一个区间DP。令 fi,j $f_{i, j}$存储区间 [i,j] $[i, j]$内的最大加分，那么三重循环分别枚举左端点、右端点和中间元素，无脑循环出来的 f1,n $f_{1, n}$即为 [1,n] $[1, n]$区间内的最大加分。在计算过程中，每次记录一下每个节点的位置，方便第二问输出。

代码

#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>int nextInt()
{int num = 0;char c;bool flag = false;while ((c = std::getchar()) == ' ' || c == 'r' || c == 't' || c == 'n');if (c == '-')flag = true;elsenum = c - 48;while (std::isdigit(c = std::getchar()))num = num * 10 + c - 48;return (flag ? -1 : 1) * num;
}typedef long long LL;LL n, f[31][31] = { 0 }, i, j, k, x, a[31] = { 0 }, node[31][31] = { 0 };void LTR(const int l, const int r)
{if (l > r)return;std::cout << node[l][r] << ' ';LTR(l, node[l][r] - 1);LTR(node[l][r] + 1, r);
}int main(int argc, char **argv)
{int n = nextInt();for (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++)f[i][j] = 1;for (int i = 1; i <= n; i++){a[i] = nextInt();f[i][i] = a[i];node[i][i] = i;}for (int i = n - 1; i >= 1; i--)for (int j = i + 1; j <= n; j++)for (int k = i; k <= j; k++)if (f[i][k - 1] * f[k + 1][j] + a[k] > f[i][j]){node[i][j] = k;f[i][j] = f[i][k - 1] * f[k + 1][j] + a[k];}std::cout << f[1][n] << std::endl;LTR(1, n);
#ifdef __EDWARD_EDITstd::();std::();
#endifreturn 0;
}