组员：盛赞宇、陈隆铭、王浩宇、付骞煜、丁文淏
交换原则：每次贪心选出的答案，一定包含在全局最优解中
国王游戏
假如i,j相邻
i:k/r[i] j:kl[i]/r[j]
max(k/r[i],kl[i]/r[i])<max(k/r[j],k*l[j]/r[i])
l[i]/r[i]>=1/r[j]
i在j前更优
i:max(pre,sum+ai)+bi
j:sum+ai+bj
max(max(pre,sum+ai)+bi,sum+ai+bj)+bj<max(max(pre,sum+aj)+bj,sum+aj+bi)+bi
max(sum+ai+bi+bj,sum+ai+aj+bj)
sum+ai+bi+bj-max()>sum+ai+bi+bj-max()
min(aj,bi)>min(ai,bj)
最大子矩阵
设dp[i]=以i结尾的最大子段和
if dp[i-1]>=0
dp[i]=dp[i-1]+a[i]
else dp[i]=a[i]
正向拓扑：求得上限
反向拓扑：求得下限
for i=1-k
if 以i作为下限&&之前没放过值
放i
else 找到点 上线最小&&未放值 放i
设1在2前放入a车间更优
a1+max(a2,b1)+b2<a2+max(a1,b2)+b1
min(a2,b1)>min(a1,b2)
ai>bi—ai升序
ai<bi—bi降序
vecbi> vec<ai