A22625. 古董
填空题
困难
知识点
题目描述
古董
题目描述
拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性：
陈列规则：所有古董按 1、……、N 编号陈列在一条长廊中，每天拍卖师只能从长廊任一端取出一件古董拍卖。
升值效应：古董拍卖顺序直接影响成交价。若第 i 件古董在第 a天拍卖，成交价为 Vi×a（Vi 为初始估价）。
价值分布：第 i 件古董的初始估价 Vi 取决于其陈列位置——从入口端开始，第 i 个展柜内的古董估价为Vi。
拍卖师需要制定最优拍卖顺序，最大化总成交额。请帮助他计算出古董全部售出后的最大收益。
输入格式
第一行：古董数量 N；
接下来 n 行：古董初始估价序列 V1～VN；
输出格式
一行整数，表示最大总收益。
输入样例
5
1
3
1
5
2输出样例
43数据范围
1≤N≤2000，1≤Vi≤1000。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 2005;
int dp[MAXN][MAXN];
int V[MAXN];
int main() {
int N;
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> V[i];
}
// 初始化长度为1的子序列（只剩一件古董时）
for (int i = 1; i <= N; ++i) {
dp[i][i] = V[i] * N;
}
// 处理长度为l的子序列（l从2到N）
for (int l = 2; l <= N; ++l) {
for (int i = 1; i + l - 1 <= N; ++i) {
int j = i + l - 1; // 子序列的右端点
int k = N - l + 1; // 当前拍卖的天数
// 取左端或右端，选择收益更大的方案
dp[i][j] = max(V[i] * k + dp[i + 1][j], V[j] * k + dp[i][j - 1]);
}
}
cout << dp[1][N] << endl;
return 0;
}答案解析
//参考代码2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// dp[i][j] 表示从第i件到第j件古董能获得的最大收益
vector<vector<long long>> dp(n, vector<long long>(n, 0));
// 初始化：单件古董在第n天拍卖（最后一天）
for (int i = 0; i < n; i++) {
dp[i][i] = (long long)v[i] * n;
}
// 区间DP：从小区间到大区间
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
int day = n - len + 1; // 当前拍卖的天数
// 选择左端古董：v[i] * day + dp[i+1][j]
// 选择右端古董：v[j] * day + dp[i][j-1]
dp[i][j] = max((long long)v[i] * day + dp[i+1][j],
(long long)v[j] * day + dp[i][j-1]);
}
}
cout << dp[0][n-1] << endl;
return 0;
}
上一题
下一题