H. Flipping Game

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

ABC327A

题目描述

Iahub 感到无聊，所以他发明了一个在纸上玩的游戏。

他写下了 $n$ 个整数 $a_{1}, a_{2}, ..., a_{n}$ 。这些整数中的每一个都只能是 $0$ 或 $1$ 。他允许进行且只能进行一次操作：任选两个下标 $i$ 和 $j$ （ $1 \leq i \leq j \leq n$ ），将区间 $[i, j]$ 内的所有 $a_{k}$ 的值翻转（即满足 $i \leq k \leq j$ ）。把 $x$ 的值翻转，就是执行 $x = 1 - x$ 操作。

游戏的目标是在恰好进行一次操作后，使序列中 $1$ 的数量最大。请编程求出 Iahub 这个小游戏的最优答案。

输入格式

输入的第一行为一个整数 $n$ （ $1 \leq n \leq 100$ ）。输入的第二行为 $n$ 个整数 $a_{1}, a_{2}, ..., a_{n}$ ，保证每个值都是 $0$ 或 $1$ 。

输出格式

输出能够获得的最多 $1$ 的数量。

输入输出样例 #1

输入 #1

5
1 0 0 1 0

输出 #1

输入输出样例 #2

输入 #2

4
1 0 0 1

输出 #2

说明/提示

在第一个样例中，可以翻转第 $2$ 到第 $5$ 个数（ $i=2, j=5$ ）。翻转后，序列变为：[1 \ 1 \ 1 \ 0 \ 1]。所以，序列中有 $4$ 个 $1$ 。无法使整个序列都变为 $1$ 。

在第二个样例中，只需要翻转第 $2$ 和第 $3$ 个数（ $i=2, j=3$ ），就可以使所有数字都变成 $1$ 。

由 ChatGPT 5 翻译

线性DP基础

Not Claimed

Status: Done
Problem: 20
Open Since: 2026-3-11 0:00
Deadline: 2026-3-31 23:59
Extension: 24 hour(s)