首页 > 题解 > bzoj 3275 Number

bzoj 3275 Number

Description

有N个正整数,需要从中选出一些数,使这些数的和最大。
若两个数a,b同时满足以下条件,则a,b不能同时被选
1:存在正整数C,使a*a+b*b=c*c
2:gcd(a,b)=1

Input

第一行一个正整数n,表示数的个数。n<=3000
第二行n个正整数a1,a2,…an

Output

最大的和

Sample Input

5

3 4 5 6 7

Sample Output

22

题解

首先想对这些数黑白染色,然后按照那种模型建图。

发现奇数不会构成勾股数,偶数不会满足第二条条件。

然后就按照奇偶染色就好了。


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×