【bzoj3158】千钧一发

2014年12月15日1,9721

Description

Input

第一行一个正整数N。

第二行共包括N个正整数,第 个正整数表示Ai。

第三行共包括N个正整数,第 个正整数表示Bi。

Output

共一行,包括一个正整数,表示在合法的选择条件下,可以获得的能量值总和的最大值。

Sample Input

4
3 4 5 12
9 8 30 9

Sample Output

39

HINT

1<=N<=1000,1<=Ai,Bi<=10^6

题解

可以证明,任意两个偶数满足2

两个奇数满足1

(2a+1)^2+(2b+1)^2=2(2a^2+2b^2+2a+2b+1)

一定不是完全平方数

所以可以用最小割解决此题

 

  • 黄学长的粉丝2016年6月10日 下午4:18 回复

    第一眼最大团给跪了.

    #1