网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P4544
2024-08-02
P4544 [USACO10NOV] Buying Feed G
思路:考虑动态规划算法。定义\(dp_{i,j}\)表示达到第\(i\)家商店时共买了\(j\)吨饲料的最小花费,那么我们可以枚举到达上一家店的饲料数\(k\):\[dp_{i,j}=(x_i-x_{i-1})\timesj^2+\min\limits_{k=j-f_{i-1}}^jdp_{i-1,k}+c_{i-1}\times(j-k)\]可以将和\(i-1\)