警示后人
查看原帖
警示后人
654709
ZCHAOSZ楼主2024/8/7 19:31

不要想太多!不要想太多!不要想太多!

考虑下面一组数据:

4
4 2 1 1
1 1 0
2 3 1

枚举所有情况:

  • 直接买 00 号药水
  • 买 22 瓶 11 号药水配置成 00 号药水
  • 买 22 号药水、33 号药水配置成 00 号药水,然后买 11 号药水配置成 00 号药水
  • 买 22 瓶 22 号药水、22 瓶 33 号药水配置成 22 瓶 11 号药水,然后配置成 00 号药水

根据枚举,该图一共 44 种情况。

可是,AC代码却计算出了 55 种情况!

这是因为对于一般情况,药水A与药水B配置成药水C的情况数转移方程为 SC=SA×SBS_C=S_A\times S_B

但是当药水A与药水A配置成药水C时,实际情况数转移方程为 SC=CSA2=SA×(SA−1)2S_C=C_{S_A}^2=\cfrac{S_A\times(S_A-1)}{2}

但是题目并没有考虑到这点,所以虽然在输入时要去重,但是计算时还是以 SC=SA×SBS_C=S_A\times S_B 来计算!

2024/8/7 19:31
加载中...