DP/Easy/CodeForces
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin>>n;
vector<int> num(n);
for(int i=0; i<n; i++){
cin>>num[i];
}
vector<int> dp(n);
vector<int> dp0(n);
vector<int> dp1(n);
if(n == 1){
if(num[0] == 0){
cout<<1;
return 0;
}
}
int c0 = 0;
int c1 = 0;
for(int i=0; i<n; i++){
if(num[i] == 0){
c0++;
}else{
c1++;
}
dp0[i] = c0;
dp1[i] = c1;
}
int check = 0;
for(int i=0; i<n; i++){
if(num[i] == 1){
check++;
}
}
if(check == n){
cout<<n-1;
return 0;
}
int a = 0;
int b = 0;
int maxi = 0;
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
int zero = dp0[i] - dp0[j];
int one = dp1[i] - dp1[j];
int next = dp0[i] - dp1[i];
int total = zero - one;
total = total < 0 ? 0 : total;
next = next < 0 ? 0 : next;
// cout<<total<<" ";
if(maxi < next){
maxi = next;
a = 1;
b = i+1;
}
if(maxi < total){
maxi = total;
a = j+2;
b = i+1;
}
}
dp[i] = maxi;
}
// cout<<endl;
// cout<<a<<" "<<b<<endl;
int ans = 0;
for(int i=0; i<n; i++){
if(i>=a-1 && i<=b-1){
if(num[i] == 0){
ans++;
}
}else{
if(num[i] == 1){
ans++;
}
}
}
cout<<ans;
}
Cpp
INFO