POJ 2181 Jumping Cows
長さPの数列が与えられて偶数秒にはその数列から数字を選んで足す、奇数秒には選んで引く。これを0秒から始める。i+1秒で選ぶ数字はi秒で選んだ数字より数列中で後のものでなくてはならない。最大和を求めよ、という問題。
DP強化週間のつもりが、たんに数列の山と谷の数字を足し引きするだけだった。
数列が増加しながら終わるときに足し忘れないよう気をつける。
以下ソース。
int main(int argc, char **argv){ int P; scanf("%d", &P); bool ascend = false; int prev = 0; int ans = 0; for(int i = 0; i < P; i++){ int t; scanf("%d", &t); if(t > prev){ if(!ascend) ans -= prev; //start to ascend ascend = true; }else{ if(ascend) ans += prev; //start to decend ascend = false; } prev = t; } //check whether progression ends in ascending printf("%d\n", (ascend ? ans + prev : ans)); return 0; }
Get up! 明日のSUPER ST@R!