三种食物,两个矿地。
每个矿地会记得最靠近的三种食物, 每一次给他们一个新的食物时,答案会加上有多个不同的食物。
求答案的最大值。
很简单的dp:
dp[i][a1][a2][b1][b2] 表示当前已经分了i个食物, a的上两个食物为a1,a2,b的上两个食物为b1,b2。
那么转移状态为: 让s[i]表示当前的食物类
dp[i][a1][a2][b1][b2] + profit(a1,a2,s[i]) -> dp[i+1][a2][s[i]][b1][b2]
类似的转移b
答案就是max(dp[n][any][any][any][any])
时间复杂度为 O(n*4^4)
空间复杂度可以利用翻滚技巧降低至 O(1)
标签:IOI,b2,Miners,a2,2007,食物,any,dp,b1 From: https://www.cnblogs.com/yonglicp/p/17833252.html