zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i表示前i块土地

f_i=\min_{j=1}^{i-1}(f_j+maxw[j-1][i]\times maxh[j-1][i])

这样的话怎么想都没有办法优化

我们发现,如果一块土地被另一块土地所包含(即长和宽都比另一块土地小),

那么只需购买那另一块土地即可,于是我们可以据此筛掉其他的土地,

只剩下一些长度递减,宽度递增的土地

那么:

f_i=\min_{j=1}^{i-1}(f_j+l[j+1]\times w[i])

设任意0\le j<k<i,若从j转移比从k转移优,那么

f_j+l[j+1]\times w[i]\le f_k+l[k+1]\times w[i] \\ w[i](l[j+1]-l[k+1])\le f_k-f_j \\ w[i]\le \frac{f_k-f_j}{l[j+1]-l[k+1]}

维护一个下凸壳就完事了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[i][sta]表示以第i只奶牛结尾,状态为sta的情况下有多少种

f[i][sta] = \sum f[i-1][sta']

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

保证这个数不会超过500000

那么就是背包了

买卖股票有3种方法:

  1. 买,第二天卖了

  2. 不买(相当于买了然后卖了)

  3. 买了,过几天再卖(相当于买了了,接下来卖了再买了)

d-1次背包即可

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

把工作按截止时间排序,如果当前时间没到截止时间,那么答案加上它的价值,然后往小根堆中插入它的价值

否则,如果他的价值比堆顶大,那么答案加上它的价值减去堆顶,删除堆顶,插入它的价值

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

53/74
Search
search