简答题 偏难
#21645

试题名称:纸牌游戏 时间限制:1.0 s 内存限制:128.0 MB 问题描述 你和小杨在玩一个纸牌游戏。 你和小杨各有 3 张牌,分别是 0、1、2。你们要进…

试题名称:纸牌游戏

时间限制:1.0 s

内存限制:128.0 MB

问题描述

你和小杨在玩一个纸牌游戏。

你和小杨各有 3 张牌,分别是 0、1、2。你们要进行N轮游戏,每轮游戏双方都要出一张牌,并按 1 战胜 0,2 战胜1,0 战胜 2 的规则决出胜负。第i轮的胜者可以获得2ai分,败者不得分,如果双方出牌相同,则算平局,二人都可获得ai分(i=1,2,…,N )。

玩了一会后,你们觉得这样太过于单调,于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部n轮的出牌,并将他的全部计划告诉你;而你从第 2 轮开始,要么继续出上一轮出的牌,要么记一次“换牌”。

游戏结束时,你换了t次牌,就要额外扣b1+…+bt分。

请计算出你最多能获得多少分。

输入描述

第一行一个整数N,表示游戏轮数。

第二行N个用单个空格隔开的非负整数a1,……,aN,意义见题目描述。

第三行N-1个用单个空格隔开的非负整数b1,…,bN-1,表示换牌的罚分,具体含义见题目描述。由于游戏进行N轮,所以你至多可以换N-1次牌。

第四行N个用单个空格隔开的整数c1,…,cN-1,依次表示小杨从第 轮至第 轮出的牌。保证ci∈0,1,2。

输出描述

一行一个整数,表示你最多获得的分数。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

4
1 2 10 100
1 100 1
1 1 2 0

样例输出 1

219

样例解释 1

你可以第1轮出 0,并在第2,3轮保持不变,如此输掉第1,2轮,但在第3轮中取胜,获得2×10=20分;随后,你可以在第4轮中以扣1分为代价改出 1,并在第4轮中取得胜利,获得2×100=200分。如此,你可以获得最高的总分20+200-1=219 。


样例输入 2

6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0

样例输出 2

56

数据规模

对于30%的测试点,保证N≤15。

对于60%的测试点,保证N≤100。

对于所有测试点,保证N≤1000;保证0≤ai,bi≤106。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int max_n = 1005; int n; int a[max_n], b[max_n], c[max_n]; int dp[3][max_n]; int result(int x, int y) {   if (x == y + 1 || x == y - 2)     return 2;   if (x == y)     return 1;   return 0; } int main() {   ios::sync_with_stdio(false);   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; ++i)     cin &gt;&gt; a[i];   for (int i = 1; i &lt; n; ++i)     cin &gt;&gt; b[i];   for (int i = 1; i &lt;= n; ++i)     cin &gt;&gt; c[i];   memset(dp, 128, sizeof(dp));   for (int k = 0; k &lt; 3; ++k) {     dp[k][0] = result(k, c[1]) * a[1];   }   for (int i = 2; i &lt;= n; ++i)     for (int j = i - 1; j &gt;= 0; --j)       for (int k = 0; k &lt; 3; ++k) {         int curr_score = result(k, c[i]) * a[i];         dp[k][j] = dp[k][j] + curr_score;         if (j &gt; 0) {           for (int l = 0; l &lt; 3; ++l) {             dp[k][j] = max(dp[k][j], dp[l][j - 1] + curr_score - b[j]);           }         }       }   int ans = -2e9, x = 0;   for (int j = 0; j &lt; n; ++j)     for (int k = 0; k &lt; 3; ++k) {       ans = max(ans, dp[k][j]);     }   cout &lt;&lt; ans &lt;&lt; '\n';   return 0; }</pre>
这道题暂未补解析。