大神的世界

想法:

感覺就是 DP 所以就用 DP 解了

考慮所有可能    0 1 2 表示倍率

ex

2 0 -> 2 0 1 , 2 0 2

考慮  Pi-2  加速跑  , Pi-1  變慢的情況， Pi 有兩種可能 1. 正常跑 ( 2 0 1)  2. 加速跑 (2 0 2)

另外  0 0   , 1 0 ,  2 1 , 2 2 不可能發生

因此下表為所有可能

0 1  -> 0 1 1 , 0 1 2
0 2  -> 0 2 0
1 1  -> 1 1 1 , 1 1 2
1 2  -> 1 2 0
2 0  -> 2 0 1 , 2 0 2
 

接著考慮 Pi+1

將 Pi+1 視為新的 Pi ，則 Pi 變 Pi-1 , Pi-1 變 Pi-2

再重新考慮所有情形 (即上表)

最終，所有可能的最大值即為所求

喔，對了，初始條件的部份可以想像存在 path0 他的分數為 0

因此初始值為 1 , 2, 1, 2, 0 倍的 path1 分數 (詳情請見程式)

#include <iostream>

using namespace std;

int main()
{
  int path;
  int weight[40];
  int rec1[5], rec2[5];

  while(cin >> path && path){
    for(int i = 0; i<path; i++)
      cin >> weight[i];

    rec2[4] = 0;
    rec2[0] = rec2[2] = weight[0];
    rec2[1] = rec2[3] = 2*weight[0];

    for(int i = 1; i<path; i++){
      for(int j = 0; j<5; j++)
        rec1[j] = rec2[j];

      rec2[0] = max(rec2[0], rec1[4] +   weight[i]);
      rec2[1] = max(rec2[1], rec1[4] + 2*weight[i]);
      rec2[2] = max(max(rec2[2], rec1[0] +   weight[i]), rec1[2] +   weight[i]);
      rec2[3] = max(max(rec2[3], rec1[0] + 2*weight[i]), rec1[2] + 2*weight[i]);
      rec2[4] = max(max(rec2[4], rec1[1]), rec1[3]);
    }

    int maximum = 0;
    for(int j = 0; j<5; j++)
      maximum = max(maximum, rec2[j]);

    cout << maximum << endl;
  }

  return 0;
}