読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


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;
}
しょげないでよBaby 眠れば治る