这一题是比较简单的动态规划，状态f[i]表示走前i个棋子时的最高分数，状态转移方程为f[i] = {max(f[j]), i > j && step[i] > step[j] + step[i]}.

AC code:

1 ude 
     
        2 #define MAX 1000  3 using namespace std;  4  5 int step[MAX];  6 int f[MAX];  7 int n;  8 int max_sum(int i)  9 {
    10     int max = 0; 11     int j; 12     for(j = 0; j < i; j++) 13     {
    14         if(f[j] > max && step[j] < step[i]) 15         {
    16             max = f[j]; 17         } 18     } 19     return max; 20 } 21 22 int main() 23 {
    24     int max; 25     while(scanf("%d", &n)!=EOF && n) 26     {
    27         memset(step, 0, sizeof(step)); 28         memset(f, 0, sizeof(f)); 29         for(int i = 0; i < n; i++) 30             scanf("%d", &step[i]); 31         f[0] = step[0]; 32         max = 0; 33         for(int i = 1; i < n; i++) 34             f[i] = max_sum(i) + step[i]; 35         for(int i = 0; i < n; i++) 36             if(f[i] > max) 37                 max = f[i]; 38         printf("%d\n", max); 39     } 40     return 0; 41 }