简答题
偏难
#7203
上机 又到周末了,同学们陆陆续续开开心心的来到机房上机。jbr也不例外,但是他到的有点晚,发现有些机位上已经有同学正在做题,有些机位还空着。细心的jbr发现,一…
上机
又到周末了,同学们陆陆续续开开心心的来到机房上机。jbr也不例外,但是他到的有点晚,发现有些机位上已经有同学正在做题,有些机位还空着。细心的jbr发现,一位同学来到机房,坐在机位i上,如果他的左右两边都空着,他将获得能力值a[i];如果当他坐下时,左边或者右边已经有一个人在上机了,他将获得能力值b[i];如果当他坐下时,他的左边右边都有人在上机,他将获得能力值c[i]。
同时他发现,已经在上机的同学不会受到刚要坐下的同学的影响,即他们的能力值只会在坐下时产生,以后不会发生变化;第一个机位左边没有机位,最后一个机位右边没有机位,无论何时坐在这两个机位上将无法获得c值。
这时jbr发现有一排机器还空着,一共有N个机位,编号1到N。这时有N位同学们陆陆续续来到机房,一个一个按照顺序坐在这排机位上。聪明的jbr想知道怎么安排座位的顺序,可以使这N位同学获得能力值的和最大呢?
时间限制:1000
内存限制:65536
输入
第一行一个整数N(1<= N <= 10000)
第二行N个数,表示a[i]
第三行N个数,表示b[i]
第四行N个数,表示c[i]
(1<= a[i],b[i],c[i] <=10000)
输出
一个整数,表示获得最大的能力值和
样例输入
4 1 2 2 4 4 3 3 1 2 1 1 2
样例输出
14
提示
第一位同学坐在第四个机位上,获得能力值4; 第二位同学坐在第三个机位上,获得能力值3; 第三位同学坐在第二个机位上,获得能力值3; 第四位同学坐在第一个机位上,获得能力值4; 总和为14。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int a[10005];
int b[10005];
int c[10005];
int d
[10005]
[4]; // 考虑前i的座位已经坐好的前i个座位最大值,0-第i个人坐下的时候两边没人,1-左边有人,2-右边有人,3-都有人
int main() {
int n;
cin >> n;
int i;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++)
cin >> b[i];
for (i = 1; i <= n; i++)
cin >> c[i];
d[1][0] = a[1];
d[1][2] = b[1];
for (i = 2; i <= n; i++) {
d[i][0] =
max(d[i - 1][3], d[i - 1][2]) +
a[i]; // 第i个位置坐下的时候两边没人,要求它先于第i-1个人被坐,也就是说第i-1个人坐下的时候一定是右边有人
d[i][1] = max(d[i - 1][0], d[i - 1][1]) + b[i];
d[i][2] = max(d[i - 1][3], d[i - 1][2]) + b[i];
d[i][3] = max(d[i - 1][0], d[i - 1][1]) + c[i];
}
cout << max(d[n][0], d[n][1]);
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// 参考答案2
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10000 + 1;
int a[N], b[N], c[N], dp[N][4];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
dp[1][0] = a[1];
dp[1][1] = -INF;
dp[1][2] = b[1];
dp[1][3] = -INF;
for (int i = 2; i <= n; i++) {
dp[i][0] = a[i] + max(dp[i - 1][2], dp[i - 1][3]);
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][1]);
dp[i][2] = b[i] + max(dp[i - 1][2], dp[i - 1][3]);
dp[i][3] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);
}
printf("%d\n", max(dp[n][0], dp[n][1]));
return 0;
}</pre><p><br/></p>
这道题暂未补解析。