topcoder DoubleLive

好题。类似 Students Camp 的优化。考虑 dp[i][j][k]dp[i][j][k] 表示当前还剩下 ii 个熊两血,jj 个一血,其中有 kk 个是人。

直接转移复杂度是 O(1)O(1) 状态共 O(n3)O(n^3) 种,复杂度 O(n3)O(n^3)

考虑怎么优化这个 dpdp 。先把状态转移的式子写出来

dp[i][j][k]=i+1i+jdp[i+1][j1][k]+j+1ki+j+1dp[i][j+1][k]+k+1i+j+1dp[i][j+1][k+1]dp[i][j][k] = \frac{i+1}{i+j}dp[i+1][j-1][k]+\frac{j+1-k}{i+j+1}dp[i][j+1][k]+\frac{k+1}{i+j+1}dp[i][j+1][k+1]

考虑最后答案求的是啥:

dp[i][j][k]×k×(i+jk)×(i+j)dp[i][j][k]\times k \times (i+j-k) \times (i+j)

于是我们考虑保留前两维,要求的是

(i+j)(kdp[i][j][k]k2+(i+j)kdp[i][j][k]k)(i+j)(-\sum_{k} dp[i][j][k] k^2 + (i+j)\sum_{k} dp[i][j][k]k)

于是我们其实只需要对所有 dp[i][j][k]dp[i][j][k] 乘上 k,k2k,k^2 做前缀和即可。

s1[i][j]=t0dp[i][j][t]t,s2[i][j]=t0dp[i][j][t]t2s_1[i][j] = \sum_{t \ge 0} dp[i][j][t]t,s_2[i][j] = \sum_{t \ge 0} dp[i][j][t]t^2 。考虑求 s1[i][j]s_1[i][j]

s1[i][j]=i+1i+js1[i+1][j1]+ji+j+1s1[i][j+1]s2[i][j]=i+1i+js2[i+1][j1]+(j1)s2[i][j+1]+s1[i][j+1]i+j+1s_1[i][j] = \frac{i+1}{i+j} s_1[i+1][j-1] + \frac{j}{i+j+1} s_1[i][j+1]\\ s_2[i][j] = \frac{i+1}{i+j} s_2[i+1][j-1] + \frac{(j-1)s_2[i][j+1] + s_1[i][j+1]}{i+j+1}

\