CF F
  • 板块学术版
  • 楼主awdec
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/14 00:54
  • 上次更新2024/8/14 01:12:07
查看原帖
CF F
285856
awdec楼主2024/8/14 00:54

思路就是 dp(应该也算背包)

dp[i][j]dp[i][j] 前 ii 个得 jj 分的 min。

然后转移:dp[i][j]=min⁡{dp[i−1][l]+calc(i,j−l)}dp[i][j]=\min\{dp[i-1][l]+calc(i,j-l)\}

其中 calc(i,j−l)calc(i,j-l) 也 dp 算一下。

具体就是对于 calc(i,j)calc(i,j) 枚举先填了多少行,然后枚举分数 jj 计算得到 jj 还要填多少列,更新一下。再枚举先填了多少列同理。特殊处理 calc(i,a[i]+b[i])calc(i,a[i]+b[i]) 和 calc(i,a[i]+b[i]−1)calc(i,a[i]+b[i]-1) 都是 a[i]×b[i]a[i]\times b[i]。

但是 wa 2。

2024/8/14 00:54
加载中...