差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/16] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/16] – [解法] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======Educational DP Contest I, | + | ======Educational DP Contest I,J, |
[[https:// | [[https:// | ||
行 61: | 行 61: | ||
===== J - Sushi ===== | ===== J - Sushi ===== | ||
- | [[https:// | + | [[https:// |
==== 問題 ==== | ==== 問題 ==== | ||
行 105: | 行 105: | ||
&+& \frac{j}{N} DP[i+1][j-1][k] \\ | &+& \frac{j}{N} DP[i+1][j-1][k] \\ | ||
&+& \frac{k}{N} DP[i][j+1][k-1] \\ | &+& \frac{k}{N} DP[i][j+1][k-1] \\ | ||
- | &+& 1 \\ | + | &+& 1 |
+ | \end{eqnarray} | ||
+ | \begin{eqnarray} | ||
DP[i][j][k] &=& \frac{N}{i+j+k}(\frac{i}{N} DP[i-1][j][k] \\ | DP[i][j][k] &=& \frac{N}{i+j+k}(\frac{i}{N} DP[i-1][j][k] \\ | ||
&+& \frac{j}{N} DP[i+1][j-1][k] \\ | &+& \frac{j}{N} DP[i+1][j-1][k] \\ | ||
&+& \frac{k}{N} DP[i][j+1][k-1] \\ | &+& \frac{k}{N} DP[i][j+1][k-1] \\ | ||
&+& 1) \\ | &+& 1) \\ | ||
- | DP[i][j][k] | + | |
\end{eqnarray} | \end{eqnarray} | ||
行 241: | 行 243: | ||
$DP[l][r]$ があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。 | $DP[l][r]$ があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。 | ||
- | * $-DP[l-1][r]+a_l$ | + | * $-DP[l+1][r]+a_l$ |
* $-DP[l][r-1]+a_{r-1}$ | * $-DP[l][r-1]+a_{r-1}$ | ||