gzwzm06

  1#include <cstdio>
  2#include <memory.h>
  3
  4const int SIZE = 1001;
  5
  6int N, arr[SIZE], dp[SIZE];
  7
  8int mark;
  9
 10void DFS( const int& s, const int& banker, const int& mine, const int& bGet, const int& mGet, const int& state )
 11{
 12    if ( banker > 21 )
 13    {
 14        if ( dp[s - 1] < mark + 1 )
 15            dp[s - 1] = mark + 1;
 16    }
 17    else if ( mine > 21 )
 18    {
 19        if ( dp[s - 1] < mark )
 20            dp[s - 1] = mark;
 21    }
 22    else if ( s == N || !( bGet | mGet ) )
 23    {
 24        if ( banker >= mine )
 25        {
 26            if ( dp[s - 1] < mark )
 27                dp[s - 1] = mark;
 28        }
 29        else if ( dp[s - 1] < mark + 1 )
 30        {
 31            dp[s - 1] = mark + 1;
 32        }
 33    }
 34    else if ( state == 1 )
 35    {
 36        if ( banker < 16 )
 37        {
 38            if ( mGet )
 39                DFS( s + 1, banker + arr[s], mine, bGet, mGet, 0 );
 40            else
 41                DFS( s + 1, banker + arr[s], mine, bGet, 0, 1 );
 42        }
 43        else {
 44            DFS( s, banker, mine, 0, mGet, 0 );
 45        }
 46    }
 47    else
 48    {
 49        if ( !bGet && banker < mine )
 50        {
 51            if ( dp[s - 1] < mark + 1 )
 52                dp[s - 1] = mark + 1;
 53        }
 54        else 
 55        {
 56            if ( bGet )
 57            {
 58                DFS( s, banker, mine, 1, 0, 1 );
 59                DFS( s + 1, banker, mine + arr[s], 1, 1, 1 );
 60            }
 61            else
 62            {
 63                DFS( s, banker, mine, 0, 0, 1 );
 64                DFS( s + 1, banker, mine + arr[s], 0, 1, 1 );
 65            }
 66        }
 67
 68    }
 69}
 70
 71int main()
 72{
 73    freopen("1.txt", "r", stdin);
 74
 75    int i;
 76
 77    while ( scanf("%d", &N), N != 0 )
 78    {
 79        for ( i = 0; i < N; ++i )
 80        {
 81            scanf("%d", &arr[i]);
 82        }
 83
 84        memset( dp, 0xff, sizeof(dp) );
 85
 86
 87        mark = 0;
 88        DFS( 4, arr[0] + arr[2], arr[1] + arr[3], 1, 1, 1 );
 89
 90        for ( i = 3; i < N - 5; ++i )
 91        {
 92            if ( dp[i] != -1 )
 93            {
 94                mark = dp[i];
 95
 96                DFS( i + 5, arr[i + 1] + arr[i + 3], arr[i + 2] + arr[i + 4], 1, 1, 1 );
 97            }
 98        }
 99
100        int ans = 0;
101
102        for ( i = 0; i < SIZE; ++i )
103        {
104            if ( dp[i] > ans )
105                ans = dp[i];
106        }
107
108        printf("%d\n", ans);
109
110    }
111
112    return 0;
113}