【BZOJ1492】【NOI2007】货币兑换

首先这玩意写\(n^2\)的dp不是很难

用\(f[i]\)记录将第\(i\)天的钱全部换成货币所能得到的最大货币数

那么每一天可以将之前某一天买入的货币全部卖掉更新答案,然后再用当前答案计算出\(f[i]\)

考虑优化这个dp:

若一个决策\(j\)比一个决策\(k\)更优,那么

$$f[j]\times r[j]\times a[i]+f[j]\times b[i]>f[k]\times r[k]\times a[i]+f[k]\times b[i]$$

$$(f[j]r[j]-f[k]r[k])\times a[i]+(f[j]-f[k])\times b[i]>0$$

假设\(f[j]>f[k]\),那么

$$\frac{f[j]r[j]-f[k]r[k]}{f[j]-f[k]}>-\frac{b[i]}{a[i]}$$

有点像斜率优化 只是要求按\(f[i]\)排序

那么可以得到一种做法:建一棵以\(f\)为关键字的平衡树维护凸线,询问就是查找斜率最靠近\(-\frac{b[i]}{a[i]}\)的一组。

不过讲道理平衡树并不是很好写的。。所以就有了强大的cdq分治

首先把每一天按照\(-\frac{b[i]}{a[i]}\)排序,然后对于过程\(solve(l,r)\):

  1. 如果\(l=r\)直接更新答案就好了
  2. 否则求个中点\(m\)
  3. 然后把编号属于\([l,m]\)的提出来,进行\(solve(l,m)\),此时这些也是按照斜率排序的
  4. 进行完\(solve(l,m)\)它们变成了按照\(f\)排序
  5. 构建\([l,m]\)形成的凸线
  6. 用\([l,m]\)更新\([m+1,r]\)
  7. \(solve(m+1,r)\)
  8. 将\([l,r]\)按\(f\)归并排序

就可以了

(讲道理写这个细节也很多啊)

2
说点什么

1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

%%%
窝根本看不懂CDQ的论文
您太强啦