首页 > 代码库 > Educational Codeforces Round 19 B. Odd sum（贪心或dp）
Educational Codeforces Round 19 B. Odd sum（贪心或dp）
题意：给出一组数，从中拿出几个，要让它们之和最大并且为奇数。
这道题给出的n不大，贪心暴力一下就可以了。(-?-;)
1.贪心
我是先把数据大于0并且为偶数的数都先加起来（保证开始的sum是偶数），数据大于0且为奇数的存在a数组里，数据小于0的存在b数组里。
然后如果有a数组有奇数个，直接加起来输出就好了。奇*奇=奇
偶数个的话就从sum中拿出a1,b1。特判一下a1(a数组里面最小的那个)和b1(b数组里最大的那个)哪个的绝对值大。
a1<b1 直接输出之前的sum，a1>=b1则输出sum+a1+b1。
注：有可能a数组或b数组里没有数储存，这个要特殊考虑一下。
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn=111111; 6 int a[maxn],b[maxn]; 7 8 int main(){ 9 int n,temp,tot1=0,tot2=0;10 long long sum=0;11 cin>>n;12 13 for(int i=1;i<=n;i++){14 cin>>temp;15 if(temp>=0){16 if(temp%2==0) sum+=temp;17 else a[tot1++]=temp;18 }19 else b[tot2++]=temp;20 }21 22 sort(b,b+tot2);23 sort(a,a+tot1);24 25 if(tot1%2==1){26 for(int i=0;i<tot1;i++) sum+=a[i];27 cout<<sum<<endl; return 0; 28 }29 30 else{31 for(int i=1;i<tot1;i++) sum+=a[i];32 for(int i=tot2-1;i>=0;i--){33 if(b[i]%2!=0){34 if(abs(b[i])>=a[0]&&a[0]!=0){cout<<sum<<endl; return 0;}35 else {cout<<sum+a[0]+b[i]<<endl; return 0;}36 }37 }38 }39 40 cout<<sum<<endl;41 return 0;42 }
2.dp
看了很久大神的dp做法，还是没看懂，（╯＾╰）。自己太菜了，dp继续学习中。）逃
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int arr=1e5+10; 6 int dp[arr][2]; 7 int a[arr]; 8 9 void maximize(int &a,int b){10 if(a<b) a=b;11 }12 13 int main(){14 fill(dp[0],dp[0]+arr*2,-1e15);15 dp[0][0]=0;16 int n;17 cin>>n;18 for(int i=1;i<=n;i++) cin>>a[i];19 for(int i=0;i<n;i++){20 for(int j=0;j<2;j++){21 maximize(dp[i+1][j],dp[i][j]);22 maximize(dp[i+1][(j+a[i+1])%2],dp[i][j]+a[i+1]);23 }24 }25 cout<<dp[n][1]<<endl;26 return 0;27 }
Educational Codeforces Round 19 B. Odd sum（贪心或dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。