TOJ470

TOJ470

題敘

https://toj.tfcis.org/oj/pro/470/
給每天訓練的成效值,在不能練續兩天訓練的前提下,問最多能獲得多少成效值

想法

每天都有取或不取兩種選擇
定義DP式 $DP[i][j]$ 表示第 $i$ 天選或不選($j=0$或$j=1$)的最大成效值
可得轉移式
$DP[i][1] = max(DP[i-1][0]+arr[i], DP[i][1])$
$DP[i][0] = max(DP[i-1][1], DP[i-1][0])$
不過實作後會發現到每次會影響到的只有上一個狀態,所以只需要記錄前一個狀態即可

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
//By Koios1143
#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;
int n;
long long tmp,ans=0,dp[2][2];
int main(){
IOS
while(cin>>n){
ans=0;
memset(dp,0,sizeof(dp));
for(int i=1 ; i<=n ; i++){
cin>>tmp;
dp[i%2][0]=max(dp[(i-1)%2][1],dp[(i-1)%2][0]);
dp[i%2][1]=max(dp[(i-1)%2][0]+tmp,dp[i%2][1]);
ans=max(dp[i%2][0],dp[i%2][1]);
dp[(i-1)%2][0] = dp[(i-1)%2][1] = 0;
}
cout<<ans<<"\n";
}
return 0;
}

複雜度

有 $2n$ 種狀態,每種狀態轉移時間複雜度為 $O(1)$
總時間複雜度為 $O(2n)$