ゲーム理論に関する興味深い問題です！

しかし、まだ完全には理解できていません...

主なアイデアは「上三角」のケースを除外することです。このケースは見た目に劣っているように見えるため、プレイヤーは最後に選ぶ可能性が高く、**必ず連続して選択されます。つまり、先手が最初と三番目を、後手が二番目を選択します**。（理性的な理解は失敗し、感覚的に理解するしかありません）

「上三角」のケースを処理した後、大きいものから順に選択できます。

しかし、サンプルがすべてWA（Wrong Answer）になることに気づきます。これは境界に大きな値がある場合があり、その場合偶数個なら最後に「強制的に」選択され、奇数個なら最も内側のものは影響を受けないためです。

注目すべきは、両側に「下三角」のケースが現れる可能性があることです。この場合、まず「下向き」の部分を取り除く必要があります。

スタックを使用したコード：

signed main() {
    read(n);
    for (register int i = 1; i <= n; ++i) {
        read(stone_value[i]);
        is_selected[i] = stone_value[i] > 0;
        if (is_selected[i])    ++total_selected;
        total_sum += stone_value[i];
    }
    bool flag = false;
    for (register  int i = 1; i <= n; ++i) {
        if (!is_selected[i]) {
            if (!flag) {
                flag = true;
                memcpy(temp_stack, stack_data, sizeof(stack_data));
                memset(stack_data, 0, sizeof(stack_data));
                stack_top = temp_stack_top; temp_stack_top = 0;
            } else {
                while (temp_stack_top)    heap[++heap_total] = stack_data[temp_stack_top], temp_stack_top--;
            }
            continue;
        }
        stack_data[++temp_stack_top] = stone_value[i];
        while (temp_stack_top > 2 && stack_data[temp_stack_top - 1] >= stack_data[temp_stack_top] && 
               stack_data[temp_stack_top - 1] >= stack_data[temp_stack_top - 2])
            --temp_stack_top, stack_data[temp_stack_top] = stack_data[temp_stack_top + 1] + stack_data[temp_stack_top - 1] - stack_data[temp_stack_top], 
            --temp_stack_top, stack_data[temp_stack_top] = stack_data[temp_stack_top + 1];
    }
    
    
    while (stack_top > 1 && temp_stack[stack_top] >= temp_stack[stack_top - 1])    heap[++heap_total] = temp_stack[stack_top], --stack_top;
    if (stack_top <= 1) {
        while (stack_top)    heap[++heap_total] = temp_stack[stack_top], stack_top--;
    } else {
        for (register int i = 1; i + 1 <= stack_top; i += 2) {
            difference += (total_selected & 1 ? 1 : -1) * (temp_stack[i] - temp_stack[i + 1]);
        }
        if (stack_top & 1)    heap[++heap_total] = temp_stack[stack_top];
    }
    int start = 1;
    while (start < temp_stack_top && stack_data[start] >= stack_data[start + 1])    heap[++heap_total] = stack_data[start], ++start;
    if (temp_stack_top - start + 1 <= 1) {
        while (temp_stack_top >= start)    heap[++heap_total] = stack_data[temp_stack_top], --temp_stack_top;
    } else {
        for (register int i = temp_stack_top; i - 1 >= start; i -= 2) {
            difference += (total_selected & 1 ? 1 : -1) * (stack_data[i] - stack_data[i - 1]);//注意!!!!!
        }
        if ((temp_stack_top - start + 1) & 1)    heap[++heap_total] = stack_data[start];
    }
    sort(heap + 1, heap + 1 + heap_total);
    int toggle = 1;
    for (register int i = heap_total; i; --i) {
        difference += toggle * heap[i];
        toggle *= -1;
    }
    printf("%lld %lld\n", (difference + total_sum) / 2, (total_sum - difference) / 2);
    return 0;
}

双方向リストを使用した簡略化版コード：

int main()
{
    read(n), right[0]=1, left[n+1]=n;
    for(int i=1;i<=n;++i)
        read(stone_value[i]), total_sum+=stone_value[i], left[i]=i-1, right[i]=i+1, is_valid[i]=(stone_value[i]!=0);
    for(int i=3;i<=n;i=right[i])
        while(is_valid[left[left[i]]] && is_valid[left[i]] && is_valid[i] && 
              stone_value[left[i]]>=stone_value[left[left[i]]] && stone_value[left[i]]>=stone_value[i])
            stone_value[i]=stone_value[left[left[i]]]+stone_value[i]-stone_value[left[i]], 
            right[left[left[left[i]]]]=i, left[i]=left[left[left[i]]];
    L=right[0], R=left[n+1];
    while(stone_value[L]>=stone_value[right[L]] && is_valid[L] && is_valid[right[L]]) 
        bonus+=stone_value[right[L]]-stone_value[L], L=right[right[L]];
    while(stone_value[R]>=stone_value[left[R]] && is_valid[R] && is_valid[left[R]]) 
        bonus+=stone_value[left[R]]-stone_value[R], R=left[left[R]];
    for(int i=L;i<=R;i=right[i])
        if(is_valid[i])
            stone_value[++total_selected]=stone_value[i];
    sort(stone_value+1,stone_value+total_selected+1,compare), stone_value[++total_selected]=bonus;
    for(int i=1;i<=total_selected;++i)
    {
        if(i&1) result_value+=stone_value[i];
        else result_value-=stone_value[i];
    }
    printf("%lld %lld",(total_sum+result_value)/2,(total_sum-result_value)/2);
    return 0;
}