956. 最高的广告牌 状压 dp

956. 最高的广告牌 状压 dp

做题结果

成功，但是效果不好，用了状压 dp, 这题范围上再大一些，状压就无法通过了

方法：状压dp

1. 求出所有子集的和

2. 取一半子集的反集的子集，如果两者和相等就加入答案

class Solution { public int tallestBillboard(int[] rods) { int ans = 0; int n = rods.length; int s = 0; for (int rod : rods) { s += rod; } int[] sums = new int[1 << n]; int mask = (1 << n); for (int i = 1; i < mask; i++){ int last =Integer.bitCount( (i&(-i))-1); int pre = i &(i-1); sums[i]=sums[pre]+rods[last]; } for(int i = 1; i < mask/2; i++){ int reverse = (i^(mask-1)); int sum = sums[i]; if(sum<=ans||sum>s/2||sums[reverse]<=ans)continue; for(int j = reverse; j > 0; j = (reverse&(j-1))){ if(sum==sums[j]) { ans = sum;break; } } } return ans; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。