好题。类似 Students Camp 的优化。考虑 dp[i][j][k] 表示当前还剩下 i 个熊两血,j 个一血,其中有 k 个是人。
直接转移复杂度是 O(1) 状态共 O(n3) 种,复杂度 O(n3) 。
考虑怎么优化这个 dp 。先把状态转移的式子写出来
dp[i][j][k]=i+ji+1dp[i+1][j−1][k]+i+j+1j+1−kdp[i][j+1][k]+i+j+1k+1dp[i][j+1][k+1]
考虑最后答案求的是啥:
dp[i][j][k]×k×(i+j−k)×(i+j)
于是我们考虑保留前两维,要求的是
(i+j)(−k∑dp[i][j][k]k2+(i+j)k∑dp[i][j][k]k)
于是我们其实只需要对所有 dp[i][j][k] 乘上 k,k2 做前缀和即可。
设 s1[i][j]=∑t≥0dp[i][j][t]t,s2[i][j]=∑t≥0dp[i][j][t]t2 。考虑求 s1[i][j]
s1[i][j]=i+ji+1s1[i+1][j−1]+i+j+1js1[i][j+1]s2[i][j]=i+ji+1s2[i+1][j−1]+i+j+1(j−1)s2[i][j+1]+s1[i][j+1]
\