首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#13124

古董 拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性: 陈列规则:所有古董按 1、……、N 编号陈列在一条长廊中,每天拍卖师只能从长廊任一端取出一件古…

古董

拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性:

陈列规则:所有古董按 1、……、N 编号陈列在一条长廊中,每天拍卖师只能从长廊任一端取出一件古董拍卖。

升值效应:古董拍卖顺序直接影响成交价。若第 i 件古董在第 a天拍卖,成交价为 Vi×a(Vi 为初始估价)。

价值分布:第 i 件古董的初始估价 Vi 取决于其陈列位置——从入口端开始,第 i 个展柜内的古董估价为Vi。

拍卖师需要制定最优拍卖顺序,最大化总成交额。请帮助他计算出古董全部售出后的最大收益。

时间限制:1000ms内存限制:256MB

输入格式

第一行:古董数量 N;

接下来 n 行:古董初始估价序列 V1~VN;

输出格式

一行整数,表示最大总收益。


输入样例

5
1
3
1
5
2

输出样例

43

数据范围:

1≤N≤2000,1≤Vi≤1000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; const int MAXN = 2005; int dp[MAXN][MAXN]; int V[MAXN]; int main() {     int N;     cin &gt;&gt; N;     for (int i = 1; i &lt;= N; ++i) {         cin &gt;&gt; V[i];     }     // 初始化长度为1的子序列(只剩一件古董时)     for (int i = 1; i &lt;= N; ++i) {         dp[i][i] = V[i] * N;     }     // 处理长度为l的子序列(l从2到N)     for (int l = 2; l &lt;= N; ++l) {         for (int i = 1; i + l - 1 &lt;= 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 &lt;&lt; dp[1][N] &lt;&lt; endl;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int main() {     int n;     cin &gt;&gt; n;     vector&lt;int&gt; v(n);     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; v[i];     }          // dp[i][j] 表示从第i件到第j件古董能获得的最大收益     vector&lt;vector&lt;long long&gt;&gt; dp(n, vector&lt;long long&gt;(n, 0));          // 初始化:单件古董在第n天拍卖(最后一天)     for (int i = 0; i &lt; n; i++) {         dp[i][i] = (long long)v[i] * n;     }          // 区间DP:从小区间到大区间     for (int len = 2; len &lt;= n; len++) {         for (int i = 0; i + len - 1 &lt; 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 &lt;&lt; dp[0][n-1] &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。