作业帮一道poi的题我们有一个可供支配的天平.如果天平的两边没有放任何重量或者两边重量一样,则天平平衡.在给出的一个砝码（每个砝码有一个重量）集合中,我们要找到两个独立的砝码子集放在
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/21 02:31:46
一道poi的题我们有一个可供支配的天平.如果天平的两边没有放任何重量或者两边重量一样,则天平平衡.在给出的一个砝码（每个砝码有一个重量）集合中,我们要找到两个独立的砝码子集放在
一道poi的题
我们有一个可供支配的天平.如果天平的两边没有放任何重量或者两边重量一样,则天平平衡.在给出的一个砝码（每个砝码有一个重量）集合中,我们要找到两个独立的砝码子集放在天平的两边使之平衡.而且我们需要放置砝码中重量最大的的重量尽可能重.
输入
在文件wag.in 中第一行有一个整数n,2
一道poi的题我们有一个可供支配的天平.如果天平的两边没有放任何重量或者两边重量一样,则天平平衡.在给出的一个砝码（每个砝码有一个重量）集合中,我们要找到两个独立的砝码子集放在
注意题目是要最重的砝码尽量重.
这道题比较可以写得比较巧妙,将砝码按重量排序,直接做背包,若某个重量被到达至少两次,那么可以用形成转移的砝码更新答案.即使某个砝码（不可能是形成该转移的砝码）被使用了两次,我们只要在左右都去除该砝码即可,不会对答案造成影响.
优化：第i次需要转移的重量,min(s[n]/2,s[i]) dwonto a[i]
program xqz;
uses math;
const maxn=1000; maxs=50000; m=maxs shr 1;
var
i,j,n,k,ans,now,t:longint;
a,s:array[0..maxn] of longint;
v:array[0..maxs] of boolean;
begin
assign(input,'wag.in'); reset(input); assign(output,'wag.out'); rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do
for j:=i+1 to n do
if a[j]s[n] shr 1 then s[i]:=s[n] shr 1;
v[0]:=true;
for i:=1 to n do
for j:=s[i] downto a[i] do
if v[j-a[i]] then
if not v[j] then v[j]:=true
else ans:=a[i];
writeln(ans);
close(input); close(output);
end.