Atcoder DP Contest pC
題敘
https://atcoder.jp/contests/dp/tasks/dp_c
每天都有三種活動可以選擇,且有各自價值
本次選擇的活動與上次選擇的不能相同,求第 $n$ 天的最大價值總和
想法
對於點 $1$ 到點 $n-1$ ,每個點都只能選兩種狀態,取其最大值即可
定義 $DP[i][j]$ 表示第 $i$ 天選擇第 $j$ 種活動時的最大價值總和
則有轉移式 $DP[i][j] = max(DP[i][s], DP[i-1][t])+arr[i][j],\ s \neq j,\ t\neq j,\ s\neq t$
Code
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> #define LL long long #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define pii pair<int,int> using namespace std; const int MaxN = 100005; int n,now,dp[MaxN][3]; int main(){ IOS while(cin>>n){ for(int i=1 ; i<=n ; i++){ for(int j=0 ; j<3 ; j++){ cin>>now; dp[i][j]=max(dp[i-1][(j+1)%3], dp[i-1][((j+2)%3)]) + now; } } int ans=0; for(int i=0 ; i<3 ; i++){ ans=max(ans, dp[n][i]); } cout<<ans<<"\n"; } return 0; }
|
複雜度
有 $3n$ 種狀態,每種狀態轉移複雜度為 $O(2)$
總複雜度 $O(n)$