2011-05-15から1日間の記事一覧
keyword 動的計画法 C++ 問題概要 正整数列X(長さN 解法 dp[i] = {iが端点になっている確率}とすれば、これはO(T*N)で求められる。その後、i+X[i]>=Tとなる確率を足し上げていけばよい。全体の計算量はO(T*N)。 感想 dp[i][k] = {iが棒kの右端になっている確…
解法 答えに関して全探索すればよい。計算量O(N^2)。
keyword 動的計画法 C++ 問題概要 正整数列X(長さN 解法 dp[i] = {iが端点になっている確率}とすれば、これはO(T*N)で求められる。その後、i+X[i]>=Tとなる確率を足し上げていけばよい。全体の計算量はO(T*N)。 感想 dp[i][k] = {iが棒kの右端になっている確…
解法 答えに関して全探索すればよい。計算量O(N^2)。