POJ 2181 Jumping Cows
http://poj.org/problem?id=2181
初め、DP ( O(P^2) ) しようとしたけどP( <=150000 )が大きすぎるのでTLEした。
わからなくて結局写経した。
O(P)すげー。おもいつけるようになりたい
↓TLE実装
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 150000; int N; int a[MAX_N]; int solve(){ int dp[2][N+1]; int t, ans = 0; //dp[t][p] := (max value when cows administrated potoin (p-1) at the time t) dp[1][0] = 0; dp[0][0] = 0; for(int i = 1; i < N; i++){ dp[1][i] = a[i-1]; } for(t = 2; t <= N; t++){ for(int i = 1; i <= N; i++){ int u = (t%2 == 0) ? -1 : 1 * a[i - 1]; dp[t%2][i] = max(dp[t%2][i-1], dp[(t+1)%2][i-1] + u); } ans = max(ans, dp[t%2][N]); } return ans; } int main(){ scanf("%d", &N); for(int i = 0; i < N; i++){ scanf("%d", &a[i]); } printf("%d\n", solve()); return 0; }
↓AC実装
#include <cstdio> #include <algorithm> using namespace std; int N; int main(){ int od = 0, ev = 0; scanf("%d", &N); for(int i = 0; i < N; i++){ int p; scanf("%d", &p); od = max(od, ev + p); ev = max(ev, od - p); } printf("%d\n", max(od, ev)); }
simple is the best