IOI 2007 Miners

发布时间 2023-11-15 10:18:59作者: yl_neo

三种食物,两个矿地。

每个矿地会记得最靠近的三种食物, 每一次给他们一个新的食物时,答案会加上有多个不同的食物。 

求答案的最大值。

 

很简单的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)