A. Flipping Game
本质上是让我们找出一段区间内\(0\)的个数大于\(1\)的个数的最多的区间,且必须进行一次操作,所以可以考虑区间\(dp\),或者最小子序列和
1 最小子序列和
\[\begin{aligned}
dp_i是以a_i结尾的最小子序列和 \\
dp_i=\min(dp_{i-1}+a[i],a[i])
\end{aligned}
\]
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
i64 ans = 0 ;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
ans += a[i];
if (!a[i]) a[i] = -1;
}
if (ans == n) ans --;
vector<int> dp(n + 1);
int k = 0;
for (int i = 1; i <= n; i ++) {
dp[i] = min(dp[i - 1] + a[i], a[i]);
if (dp[i] < dp[k])
k = i;
}
cout << ans - dp[k] << '\n';
return 0;
}
2 区间dp
\[\begin{aligned}
dp_{i,j}&为从i到j区间所有元素取反的和 \\
dp_{i,j}&=\max(dp_{i+1,j}+(1-a_i),dp_{i,j-1}+(1-a_j))
\end{aligned}
\]
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1), pre(n + 1);
vector dp(n + 2, vector<int>(n + 2));
int ans = 0 ;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
dp[i][i] = a[i] ^ 1;
}
for (int len = 1; len <= n; len ++) {//枚举区间长度
for (int i = 1; i + len - 1 <= n; i ++) {
int j = i + len - 1;
dp[i][j] = max(dp[i + 1][j] + (a[i] ^ 1), dp[i][j - 1] + (a[j] ^ 1));
ans = max(ans, pre[i - 1] + dp[i][j] + pre[n] - pre[j]);
}
}
cout << ans << '\n';
return 0;
}