C++ 一维DP数组解决：NOI发题顺序优化问题

多年过去后，Su_Zipei 成为了一名NOI赛场的工作人员。一年一度的NOI到了，这次他负责分发纸质题面，从一侧的办公室中拿出 n 个题册，要发给 n 名同学，最后需要回到办公室，注意他只能走一个来回，也就是说，如果一名同学在 Su_Zipei 从 1 到 n 的过程中没有拿到题册，那这名同学必须在 Su_Zipei 从 n 到 1 的过程中拿到题册。

这 n 名同学坐成一排，离办公室最近的标号为 1 ，最远的标号为 n 。

虽然并不是拿到题册后就可以翻看，但每名同学还是希望自己可以尽快拿到题册，这样可以使得他们开心，除此之外，由于某些神秘原因，发题的顺序也会影响大家的心情。

具体的，每名同学都有一个开心值 H ，若他给第 j 名同学发题前刚刚为第 i 名同学发题，则第 j 名同学就会高兴，产生高兴指数 W = H_i * H_j

这样，如果他按一定的方式调整发题顺序，可以得到更高的高兴指数，作为一名老年选手，Su_Zipei 希望所有人的高兴指数之和最大，请你帮忙算出最大的高兴指数之和，第一个拿到题册的同学不产生高兴指数。

样例输入：

3
7 1 9

样例输出：

72

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
vector<int> dp(n, 0);
dp[0] = h[0] * h[1];
for (int i = 1; i < n - 1; i++) {
int maxW = 0;
for (int j = 0; j < i; j++) {
maxW = max(maxW, dp[j] + h[j] * h[i + 1]);
}
dp[i] = maxW;
}
int maxW = 0;
for (int i = 0; i < n - 1; i++) {
maxW = max(maxW, dp[i] + h[i] * h[n - 1]);
}
cout << maxW << endl;
return 0;
}

代码解释：

代码使用了一维DP数组 dp 来存储中间结果，dp[i] 表示前 i+1 个同学的最大高兴指数之和。代码首先初始化 dp[0] 为第一个同学和第二个同学产生的高兴指数。然后遍历从第二个同学到倒数第二个同学，对于每个同学 i，遍历其前面所有的同学 j，计算出以 i 结尾的最大高兴指数之和，并更新 dp[i]。最后遍历所有同学，计算出最终的最大高兴指数之和。

该代码通过动态规划的方式，避免了重复计算，提高了代码效率。