問題文 [1,n]のうちa*i+b*jで表せない数が何個あるか数える問題です。入力a,b,nは10^6以下の整数でi,jは非負整数です。動的計画法で解ける問題でした。dp[x] := 整数xをa*i+b*jで表すことができるかどうか(0 or 1)で計算しました。dp[0]を1で初期化し、iを0…

問題文 DPで解く問題です。ボードが数字であるとき、その数字の後ろに右か下の位置の数字をつなげることができます。dp[y][x]にボードの(x,y)の位置からつくることのできる最大の数字が入るように計算していきます。右下からDPテーブルを埋めて行きましょう…

問題文 スタートからゴールまでの経路が何通りあるか調べる問題です。典型的な動的計画法で解くことができます。 動的計画法については最強最速アルゴリズマー養成講座のアルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だったの説明がわ…

問題文 DPで解ける問題です。 DP[数列のi番目][途中の計算結果]：組み合わせ数 となるように計算します。 JOI君は途中の計算結果が0以上20以下のものしか扱えないようです。DP[n-2][ a[n-1] ]が解となります。 #include <iostream> using namespace std; int main(){ i</iostream>…

問題文 DPで解けます。i段目の上がり方がA[i]通りあるとすると i段目に来るためには1つ下の段か、2つ下の段か、3つ下の段から来るはずなので A[i]はA[i-1]+A[i-2]+A[i-3]で求まります。解は(A[n]/365/10)+1を出力します。 #include <iostream> using namespace std; in</iostream>…