链接：https://vjudge.net/problem/OpenJ_Bailian-4150
思路：状态设计非常的重要，我们考虑某一个位置与左右坐人的顺序，则设计状态dp[][]，dp[0][i]表示i在i+1之前入座，dp[1][i]表示i在i-1之后入座，则有
dp[0][i] = max(dp[0][i-1]+b[i],dp[1][i-1]+a[i])
dp[1][i] = max(dp[0][i-1]+c[i],dp[1][i-1]+b[i])
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10001;
int a[maxn],b[maxn],c[maxn];
int n;
int dp[2][maxn];
int main(){
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]);
memset(dp,0,sizeof(dp));
dp[0][1] = a[1];dp[1][1] = b[1];
for(int i=2;i<=n;++i){
dp[0][i] = max(dp[0][i-1]+b[i],dp[1][i-1]+a[i]);
dp[1][i] = max(dp[0][i-1]+c[i],dp[1][i-1]+b[i]);
}
printf("%dn",dp[0][n]);
return 0;
}
|
近期评论