第49场周赛第二题
法一 DP
直接cv大佬整理的思路:
状态表示:
集合:
f[i][0] 从前i个元素中选择且和为奇数的最大元素和
f[i][1] 从前i个元素中选择且和为偶数的最大元素和
属性:max
状态转移,
如果不选a[i]:
f[i][0] = f[i - 1][0]、f[i][1] = f[i - 1][1];
如果选a[i]:
如果a[i]是奇数,那么f[i][0] = max(f[i][0], f[i - 1][1] + a[i])、f[i][1] = max(f[i][1], f[i - 1][0] + a[i]);
如果a[i]是偶数,那么f[i][1] = max(f[i][1], f[i - 1][1] + a[i])、f[i][0] = max(f[i][0], f[i - 1][0] + a[i]);
答案:f[n][0]
初始化:f[0][0]=-0x3f3f3f3f(刚开始不可能选出奇数和)
我的代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int f[N][2];
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[0][0]=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
f[i][0]=f[i-1][0];
f[i][1]=f[i-1][1];
if(abs(a[i]%2)==1){//奇数
f[i][1]=max(f[i-1][0]+a[i],f[i][1]);//偶
f[i][0]=max(f[i-1][1]+a[i],f[i][0]);//奇
}else{//偶
f[i][1]=max(f[i-1][1]+a[i],f[i][1]);
f[i][0]=max(f[i-1][0]+a[i],f[i][0]);
}
}
cout << f[n][0];
return 0;
}
法二 分类讨论
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
typedef pair<int,int> PII;
int a[N];
vector<int> js,os;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n,greater<int>());
int big_0_j=0;
int has_zs=0;
int has_fs=0;
for(int i=0;i<n;i++){
if(a[i]%2==0)os.push_back(a[i]);
else {
js.push_back(a[i]);
if(a[i]>0){
big_0_j++;
has_zs=1;
}
if(a[i]<0)has_fs=1;
}
}
int ans=0;
for(int i=0;i<os.size();i++){
if(os[i]>0){
ans+=os[i];
}else{
break;
}
}
if(big_0_j%2!=0){//大于0的奇数个
//奇数个
for(int i=0;i<big_0_j;i++){
ans+=js[i];
}
}else{
//大于0的偶然数个
if(has_fs&&has_zs&&js[big_0_j-1]<=abs(js[big_0_j])){//有负的有正的
big_0_j-=1;
}else if(has_fs&&has_zs&&js[big_0_j-1]>abs(js[big_0_j])){
big_0_j+=1;
}
else if(has_fs&&!has_zs){
big_0_j=1;
}
else if(!has_fs&&has_zs){
big_0_j-=1;
}
for(int i=0;i<big_0_j;i++){
ans+=js[i];
}
}
cout<<ans;
return 0;
}