五合一网站建设方案/凡科建站下载

今天来给大家讲 Vaction 这道题目

题目传送门(洛谷)

题意翻译
太郎的暑假有$n$天，第$i$天他可以选择做以下三种事情：

游泳，获得$a_i$点幸福值。
捉虫，获得$b_i$点幸福值。
写作业，获得$c_i$点幸福值。
但他不能连续两天进行同一种活动，请求出最多可以获得多少幸福值。

输入输出样例
输入
3
10 40 70
20 50 80
30 60 90
输出
210

思路

这题挺水的,方法也挺多,但是由于本人刚刚学完$dp$所以运用了动态规划的方法
设$dp[i][0]$ 表示第$i$天选择游泳可获得的最大幸福值
设$dp[i][1]$ 表示第$i$天选择捉虫可获得的最大幸福值
设$dp[i][2]$ 表示第$i$天选择写作业可获得的最大幸福值

由于这一天只能选择与上一天不同的活动 所以状态转移方程为
$dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i]$
$dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i]$
$dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i]$

最后 我们输出$max(dp[n][0],dp[n][1],dp[n][2])$即可

代码

#include<bits/stdc++.h>//万能头吖
using namespace std;
int n,a[100005],b[100005],c[100005],dp[100005][3];//定义数组
int main(){cin>>n;//输入nfor(int i=1;i<=n;++i)cin>>a[i]>>b[i]>>c[i];//输出a[i],b[i],c[i]for(int i=1;i<=n;++i){//状态转移dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];}cout<<max(max(dp[n][0],dp[n][1]),dp[n][2]);//输出dp[n][0],dp[n][1],dp[n][2]的最大值 return 0;//末尾打上return 0是一种美德
}