上海计算机学会2023年8月月赛C++丙组T3假期

假期

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

题目描述

假期共有 n 天，每天可以在三件事中选择做一件事：

• 如果在第 i 天选择玩耍，则可以获得 xi​ 点分数
• 如果在第 i 天选择刷题，则可以获得 yi​ 点分数
• 如果在第 i 天选择躺平，则可以获得 zi​ 点分数

如果要求每天做的事情不能与前一天相同，则如何安排假期的活动，才能使得分数之和达到最大？

输入格式

• 第一行：单个整数 n
• 第二行到第 n+1 行：第 i+1 行有三个整数 xi​，yi​ 与 zi​。

输出格式

• 单个整数：表示最大分数

数据范围

• 30% 的分数，1≤n≤10
• 60% 的分数，1≤n≤300
• 100% 的分数，1≤n≤200,000
• 0≤xi​≤10,000
• 0≤yi​≤10,000
• 0≤zi​≤10,000

样例数据

输入:
3
100 1 1
1 100 1
1 1 100
输出:
300
 

解析：本题采用递推算法，详见代码

#include<bits/stdc++.h>
using namespace std;
int n;
int x[200005];
int y[200005];
int z[200005];
int main() {
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>z[i];
        x[i]+=max(y[i-1],z[i-1]);//第i天玩耍可以获得的最大值
        y[i]+=max(x[i-1],z[i-1]);//第i天刷题可以获得的最大值
        z[i]+=max(x[i-1],y[i-1]);//第i天躺平可以获得的最大值
    }
    cout<<max(x[n],max(y[n],z[n]));//第n天三种情况的最大值即为答案
    return 0;
}