Colored Papers

Problem Statement

在上语文课时，不安分的水晶经常因为无聊去打扰正在认真听课的你，你现在已经被他搞得不耐烦了。

这时，你的目光扫到了作文纸，你突发奇想，通过作文纸设计了一个游戏，心想这下应该能支开水晶了。

将作文纸上的格子看成一个长度为 n 的数组，你必须将数组中的每一个单元格都涂成红色或者蓝色。

如果把第 i 个单元格涂成红色，那么你会获得 a_i 分数；如果把它涂成蓝色，那么你会获得 b_i分数；

对于第 i 个单元格来说，每有一个与它颜色相同的相邻单元格，那么就会额外获得一次 c_i分数。

因为每一个单元格最多有两个相邻单元格，所以它最多获得两次额外分数。

请你设计一种涂颜色的方法，使得最终每个单元格的得分和最大。

Input

第一行输入一个 \(n (2 \leq n \leq 1000)\) ，代表数组的大小。

第二行输入 \(n\) 个整数 \(a_{1},a_{2},a_{3},...,a_{n} (1 \leq a_{i} \leq 5000)\) 代表每个单元格被涂成红色的得分。_

第三行输入 \(n\) 个整数 \(b_{1},b_{2},b_{3},...,b_{n} (1 \leq b_{i} \leq 5000)\) 代表每个单元格被涂成蓝色的得分。_

第四行输入 \(n\) 个整数 \(c_{1},c_{2},c_{3},...,c_{n} (1 \leq c_{i} \leq 5000)\) 代表每个单元格每有一个与它颜色相同的相邻单元格时的额外得分。

Output

输出一行一个整数，代表能够获得的最大分数和。

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{   
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n;
    int a[n+1];
    int b[n+1];
    int c[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];//涂红色
    for(int i=1;i<=n;i++)cin>>b[i];//涂蓝色
    for(int i=1;i<=n;i++)cin>>c[i];//加分
    int dp[n+1][2];//第二位两个状态：0代表这个方格涂红色 1代表涂蓝色
    dp[1][0] = a[1];
    dp[1][1] = b[1];
    for(int i=2;i<=n;i++)
    {	//状态转移方程
        dp[i][0] = max(dp[i-1][0]+a[i]+c[i-1]+c[i],dp[i-1][1]+a[i]);
        dp[i][1] = max(dp[i-1][1]+b[i]+c[i-1]+c[i],dp[i-1][0]+b[i]);
    }
	//输出两个状态下的最优解
    cout << max(dp[n][0],dp[n][1]);
    return 0;
}