BadNeighbors TCCC '04 Round 4 easy

program topcoder
  • 初めてDPっぽい問題のDPっぽい解答方針を自分で立てられた気がする。
    • DPというのは、「昨日までの結果が分かれば今日の結果はすぐわかっちゃうぜ」という問題に対する汎用的なメソッドだということがやっと理解出来た。
    • 初めてDPを習ったのは多分大学3年の算法数理工学の授業だったから理解するのに10年弱かかってるな。

この問題では最初の要素は最後の要素に隣接しているという設定なので、ちょっと工夫が必要。家の番号を1 から nとする。1とnは隣接しているので、1とnの両方が解に含まれているということはあり得ない。従って、「1を含まない」か「nを含まない」のどちらかの条件を満たす組み合わせの中から最適な物を選べば良い。1を含まないような組み合わせに対する最適値は、2からnの家に対して普通にDPをやれば分かる。この時、2とnは隣接していないので、終端に気を使う必要が無い。nを含まない組み合わせに対する最適値も同様。

  • 実は、n番目を敢えて外した方が良い場合もあるということに結構長い間気付かずはまっていた。
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class BadNeighbors{
public:

  int dp(vector<int>& don, int s, int e){
    int use = 0, notUse = 0;
    for(int i = s; i < e; i++){
      swap(use, notUse);
      use += don[i];
      use = max(use, notUse);
    }
    return max(use, notUse);
  }

  int maxDonations(vector <int> donations){ 
    return max(dp(donations, 0, donations.size() - 1),
	       dp(donations, 1, donations.size()));
  }



};