其中|S|表示S的元素个数。魔理沙将会使用若干次八卦炉，直到把所有毛玉全部击中。任意两次攻击的范围均不重叠。最后得到的分值为每次攻击分值之和。现在请你计算出能够得到的最大分值。
分析：这道题目像一次函数，用tan（α）就可表示Y=KX+B中的K值了（具体用数学演算，找到函数与X坐标轴交点后再在函数上任意找一点来推断就可以了。）再用DP，状态转移方程：f[i]:=max(f[i],f[j]+(sum1[i]-sum1[j])*(sum2[i]-sum2[j])/(sum[i]-sum[j]));
附上代码：
uses math; const maxn=3000; var x,y,value,mul,sum,sum1,sum2:array [0..maxn] of longint; f,compare:array [0..maxn] of double; flag:array [0..maxn] of boolean; n,angle,times:longint; real1:double; procedure init; var i:longint; begin readln(n); for i:=1 to n do readln(x[i],y[i],value[i],mul[i]); readln(angle); real1:=tan(angle*pi/180); for i:=1 to n do compare[i]:=y[i]-real1*x[i]; end; procedure qsort(l,r:longint); var i,j,temp:longint; test,mid:double; begin i:=l; j:=r; mid:=compare[(i+j) div 2]; repeat while compare[i]<mid do inc(i); while compare[j]>mid do dec(j); if i<=j then begin test:=compare[i]; compare[i]:=compare[j]; compare[j]:=test; temp:=x[i]; x[i]:=x[j]; x[j]:=temp; temp:=value[i]; value[i]:=value[j]; value[j]:=temp; temp:=y[i]; y[i]:=y[j]; y[j]:=temp; temp:=mul[i]; mul[i]:=mul[j]; mul[j]:=temp; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; function max(a,b:double):double; begin if a>b then exit(a); exit(b); end; procedure prepare; var i,j:longint; begin qsort(1,n); for i:=1 to n do if not flag[i] then begin flag[i]:=true; inc(times); inc(sum[times]); sum1[times]:=sum1[times]+value[i]; sum2[times]:=sum2[times]+mul[i]; for j:=i+1 to n do if not flag[j] then begin if compare[j]=compare[i] then begin flag[j]:=true; inc(sum[times]); sum1[times]:=sum1[times]+value[j]; sum2[times]:=sum2[times]+mul[j]; end; end; end; end; procedure main; var i,j:longint; begin for i:=2 to times do begin sum[i]:=sum[i]+sum[i-1]; sum1[i]:=sum1[i]+sum1[i-1]; sum2[i]:=sum2[i]+sum2[i-1]; end; for i:=1 to times do for j:=0 to i-1 do f[i]:=max(f[i],f[j]+(sum1[i]-sum1[j])*(sum2[i]-sum2[j])/(sum[i]-sum[j])); writeln(f[times]:0:3); end; begin init; prepare; main; end.
