AOJ 2106 : Enegy Transporter

問題リンク : Enegy Transporter | Aizu Online Judge

問題概要：
n個のノードが一直線上につながれている
ノードはそれぞれ値を持つ
両端のノードと値が０のノード以外のノードは自分の値をマイナス１することで
右のノードの値に左のノードの値を加えることができる
一番左のノードの値を最大化せよ

解法：
動的計画法を行う
dp[i][j][k] := ノードkの値がiでノードk+1のノードの値がjという状態を作れるか？

for i 1..N-1 //今みているノードの番号
  int R = node[i+1] //今見ているノードの右隣のノードの値,ひとつしかない
  for L 0..160 //今みているノードの左隣のノードの値, 複数通り考えられるのでループを使う
    for M 0..160 //今みているノードの値,複数考えられるのでループ
      if dp[L][M][i&1] == false //この状態をつくれないなら処理しない
        continue
      else 
        dp[M][R][(i+1)&1] = true     //加える操作を行わない場合
        dp[M-1][R+L][(i+1)&1] = true //加える操作を行う場合

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
#define MAX 160 
using namespace std;

bool dp[MAX][MAX][2];
 
int main()
{
  int T;
  while(cin >> T)
    {
      while(T--)
	{
	  rep(i,MAX)rep(j,MAX)rep(l,2)dp[i][j][l] = false;
	  int N;
	  cin >> N;
	  int input[N];
	  rep(i,N) cin >> input[i];
       
	  if(N <= 2)
	    {
	      cout << input[N-1] << endl;
	      continue;
	    }
       
	  int ans = input[N-1];
 
	  REP(cur,1,N-1)
	    {
	      dp[input[cur-1]][input[cur]][cur&1] = true;
	      int R = input[cur+1];
	      rep(L,MAX)
		{
		  rep(M,MAX)
		    {
		      if(!dp[L][M][cur&1])continue;
		      if(M == 0)
			{
			  if(cur+2 < N) dp[M][R][(cur+1)&1] = true;
			  else          ans = max(ans,R);
			}
		      else
			{
			  if(cur+2 < N)
			    {
			      dp[M][R][(cur+1)&1] = true;
			      dp[M-1][R+L][(cur+1)&1] = true;
			    }
			  else ans = max(ans,R+L);
			}
		    }
		}
	      rep(i,MAX)rep(j,MAX)dp[i][j][cur&1] = false;
	    }
	  
	  cout << ans << endl;      
	}
    }
  return 0;
}