Untitled
user_0483151
plain_text
6 months ago
1.4 kB
3
Indexable
// muzik #include <bits/stdc++.h> #define cook '\n' #define maxn #define Task "bai1" using namespace std; int n; vector<int> v,dp,tr,step ; int Find(int pos) { if ( dp[pos] == dp[pos-3]+v[pos]+v[pos-1] ) return 1 ; if ( dp[pos] == dp[pos-2]+v[pos] ) return 2; return 3 ; } int solve(int pos) { if ( tr[pos] == 1 ) { step.push_back(pos) ; step.push_back(pos-1) ; return pos-3 ; } if ( tr[pos] == 2 ) { step.push_back(pos) ; return pos-2; } return pos-1; } int main() { ios_base::sync_with_stdio(0) ; cin.tie(nullptr) ; if(fopen(Task".INP","r")) { freopen(Task".INP","r",stdin); freopen(Task".OUT","w",stdout); } cin >> n; v.resize(n+1) ; dp.resize(n+1) ; tr.resize(n+1) ; for ( int i = 1; i <= n; i++ ) cin >> v[i] ; dp[1] = max(v[1],0); if (dp[1]==v[1]) tr[1]=2; dp[2] = max({dp[1]+v[2],0,dp[1]}); if (dp[2]==dp[1]+v[2]) tr[2]=1; else if (dp[2]==dp[1]) tr[2]=3; for ( int i = 3; i <= n; i++ ) { dp[i] = max({dp[i-3]+v[i]+v[i-1],dp[i-2]+v[i],dp[i-1]}) ; tr[i] = Find(i); } cout << dp[n] << cook ; int pos = n; while ( pos > 0 ) pos = solve(pos) ; for ( int i = step.size(); i ; i-- ) cout << step[i-1] << " " ; }
Editor is loading...
Leave a Comment