C - Vacation Educational DP Contest
Problem Link: https://atcoder.jp/contests/dp/tasks/dp_c
Problem Statement:
Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.
The vacation consists of
N days. For each
i(1≤i≤N), Taro will choose one of the following activities and do it on the
i-th day:
A: Swim in the sea. Gain
ai points of happiness.
B: Catch bugs in the mountains. Gain
bi points of happiness.
C: Do homework at home. Gain
ci points of happiness.
As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.
Find the maximum possible total points of happiness that Taro gains.
Procedure:
[
Sample Output 1
3 10 40 70 20 50 80 30 60 90
DAY 0 : A = 10; B = 40; C = 70;
DAY 1 : A = max(40+20, 70+20); B = max(10+50, 70+50); C = max(10+80, 40+80); (90,120,120)
DAY 2 : A = max(120+30, 120+30); B = max(90+60, 120+60); C = max(90+90, 120+90);(150,180,210)
]
SOLUTION:
// Problem: D - D
// Contest: Virtual Judge - M>I>G>A 2021
// URL: https://vjudge.net/contest/430255#problem/D
// Memory Limit: 1048 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
/*
██╗ ██╗ ███╗ ███╗ ██╗ ████████╗
██║ ██║ ████╗ ████║ ██║ ╚══██╔══╝
═════════██╠════════██╠═══██╔████╔██╠═══██╠══════██╠══════════
██║ ██║ ██║╚██╔╝██║ ██║ ██║
███████╗ ██║ ██║ ╚═╝ ██║ ██║ ██║
╚══════╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝
...Brilliants are those who know their limits*/
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long int
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define DISPV(v) {for(auto x___: v) cout << x___ << " "; cout << endl;}
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define UNIQUE(X) (X).erase(unique(com(X)),(X).end())
#define go(i,sp) for(auto i=sp.begin();i!=sp.end();i++)
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define do(i, a, b) for (ll i=(a);i<=(b);i++)
#define DO(i, b, a) for (ll i=(b)-1;i>=(a);i--)
#define dbg(x) cout << #x << " is " << x << endl
#define inp freopen("inp.txt", "r", stdin)
#define IN(a,b) a.insert(a.end(), b.begin(), b.end())
#define s(v) ((int)(v).size())
#define deb(x) cout<<x<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define com(s) (s).begin(),(s).end()
#define CASES int tc;cin>>tc;while(tc--)
#define pII pair<ll,ll>
#define pb push_back
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define endl '\n'
using namespace std;
const int MAXN = 1e6+5; const ll INF = 1e18;
const int M = 1e9+7;
//POWER-SIEVE-DFS-VISIT-GCD-MUL-POW;
//bool isprime[MAXN];
//vector<ll>ad[maxN],VISIT(maxN,0);
//ll gcd(ll A, ll B) {return B == 0 ? A : gcd(B, A % B);}
//ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
//ll logtwo(ll n){if(n==1)return 0;return logtwo(n/2)+1;}
//ll sum_digit(ll n){ ll a=0,i; for(i=n;i>0;i=i/10){ a+=(i%10);} return a; }
//ll num_digit(ll n){ ll a=0,i; for(i=n;i>0;i=i/10){ a++;} return a; }
//void dec_digit(ll n,ll b[]){ ll a=0,i; for(i=n;i>0;i=i/10,a++) b[a]=i%10; }
//ll ncr(ll n,ll r,ll m){ if((n<0) || (r<0) || (n<r)) return 0; return ((((fact[n] * MI[r]) % m ) * MI[n-r] ) % m); }
//ll calculateNcR(ll n, ll r){ if(n<r)return 0; ll p=1,k=1;if(n-r<r)r=n-r;if(r!=0){while(r){p*=n;k*=r;ll m=gcd(p, k);p/=m;k/=m;n--;r--;}}
//void DFS(ll x){ VISIT[x] = 2;for (ll i = 0; i<ad[x].size(); ++i){if(VISIT[ad[x][i]]==0){DFS(ad[x][i]);}}}
//long long POW(long long A, long long N, long long MOD) { if (N == 0) return 1 % MOD; if (N == 1) return A % MOD; long long tmp = POW(A, N / 2, MOD) % MOD; if (N % 2) return ((tmp * tmp) % MOD * A % MOD) % MOD; else return (tmp * tmp) % MOD;}
//long long MUL(long long A, long long B, long long MOD) {long long r = 0;while (B) {r = (r + (A * (B % 2) % MOD)) % MOD;A = (A + A) % MOD;B /= 2;}return r;}
//void SIEVE(ll x){for(ll i=2; i<=x*x; i++)isprime[i]=true;for(ll i=3; i<=x*x; i+=2){if(isprime[i]==true) {for(ll J=i*i; J<=x*x; J+=i)isprime[J]=false;}}}
//DEBUGGING-TOOL
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr <<*it << " = " << a << endl;
err(++it, args...);
}
///
int dx4[] = {0, 0, 1, -1}; int dy4[] = {1, -1, 0, 0};
int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}; int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1}; //King's move
int FX[] = {-2, -2, -1, -1, 1, 1, 2, 2};int FY[] = {-1, 1, -2, 2, -2, 2, -1, 1}; //Knight's move
//CODE
void _CODE() {
ll n,m,l,r,d,a,b,k,u,p,q,x,y,z,mn,mx,rem,ans,res=0,c=0;
cin >> n;
vector<ll>dp(3);
while(n--){
vector<ll>v(3,0), new_dp(3,0);
rep(i, 0, 3)cin >> v[i];
rep(i, 0, 3){
rep(ii, 0, 3){
if(i!=ii) new_dp[ii] = max(new_dp[ii],dp[i]+v[ii]);
}
}
dp = new_dp;
}
cout << max({dp[0],dp[1],dp[2]}) << '\n';
}
int32_t main() {
IO;
//CASES {
_CODE();
//}
}
/** ALHAMDULILLAH **/
Comments
Post a Comment