AT4524 Vacation

zzr1208 · 2023-11-14 20:42:06 · 题解

题目传送门

题目传送门 luogu

题目传送门 AtCoder

题目翻译

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

• 游泳，获得 a_i 点幸福值。
• 捉虫，获得 b_i 点幸福值。
• 写作业，获得 c_i 点幸福值。

但他不能连续两天进行同一种活动，请求出最多可以获得多少幸福值。

Solution:

这道题是一道dp的题。

数组及含义:

int dp[100010][3];//dp数组，表示在第i天执行了对应的操作后最大的幸福值
int a[100010],b[100010],c[100010];//题目中的a[i],b[i],c[i]

dp[][0]:第一种操作
dp[][1]:第二种操作
dp[][2]:第三种操作

转移方程：

注意:不能连续两天进行同一种活动，并且，则转移方程为：

AC Code:

#include <bits/stdc++.h>
using namespace std;
int dp[100010][3];
int a[100010],b[100010],c[100010];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>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(dp[n][0],max(dp[n][1],dp[n][2]));
    return 0;
}

AC记录