yukicoder No.45 回転寿司
問題概要
回転ずしで美味しさが最大になるように寿司を取る。ただし2回連続ですしを取ることはできない。
解法
1をすしを取る、0をとらない、とすると、
1010
1001
0101
0010
のようなパターンが続くことになる。それを漸化式で表すと、
dp[i][0] = max(dp[i - 1][1], dp[i - 2][1]);
dp[i][1] = max(dp[i - 1][0] + v[i], dp[i - 2][0] + v[i]);
の2式になる。i番目にすしを取らないのはi-1番目とi-2番目にすしをとった物の最大値から求まり、i番目にすしを取るのはi-1番目とi-2番目にすしをとらない時から求まる。
ミス
特にない。
コード
#include <iostream> #include <algorithm> #include <functional> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) int main(void){ int n; cin >> n; vector<int> v(n); rep(i, n) cin >> v[i]; int dp[1001][2]; dp[0][0] = 0; dp[0][1] = v[0]; dp[1][0] = v[0]; dp[1][1] = v[1]; reps(i, 2, n){ dp[i][0] = max(dp[i - 1][1], dp[i - 2][1]); dp[i][1] = max(dp[i - 1][0] + v[i], dp[i - 2][0] + v[i]); } int ans = max(dp[n - 1][0], dp[n - 1][1]); printf("%d\n", ans); return 0; }