プログラミングコンテストでの動的計画法
2. はじめに • 「動的計画法」は英語で 「Dynamic Programming」 と言います． • 略して「DP」とよく呼ばれます． • スライドでも以後使います． 4. ナップサック問題とは？ • n 個の品物がある • 品物 i は重さ wi, 価値 vi • 重さの合計が U を超えないように選ぶ – 1 つの品物は 1 つまで • この時の価値の合計の最大値は？ 品物 1 品物 2 品物 n 重さ w1 重さ w2 ・・・ 重さ wn 価値 v1 価値 v2 価値 vn 5. ナップサック問題の例 品物 1 品物 2 品物 3 品物 4 U=5 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v2 = 2 v3 = 4 v4 = 2 品物 1 品物 2 品物 3 品物 4 答え 7 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v
最長増加部分列・最長共通部分列 [いかたこのたこつぼ]
ある数列や文字列 $A=\{a_1,a_2,...,a_n\}$ がある時、部分列（Subsequence）とは、$A$ からいくつかの要素を抽出した列。飛び飛びでもよいが、順番は元から変わってはいけない。 $A$の部分列 $B=\{a_i,a_j,...,a_k\}$、ただし $1 \le i \lt j \lt ... \lt k \le n$
Kadane’s Algorithm | 最大部分配列 問題 - Ark's Blog
DPについて調べてたらKadane's algorithmという聞いたことないアルゴリズムが出てきたので調べてみた。 Kadane's algorithmは、最大部分配列問題(maximum subarray problem)をで解くアルゴリズムみたいです。 以下は、最大部分配列問題とそれを解くアルゴリズムの解説です。 最大部分配列問題とは 最大部分配列問題(maximum subarray problem)とは、与えられた配列に対して、その(連続した)部分配列のうち和が最大となるものの値を求める問題のことです。 形式化すると次のようになります。（添字は0-basedとします） 入力: 大きさの数列 出力: 以下、 とおきます。 解法 全探索1: 全探索2: Divide and Conquer: Kadane's algorithm: 全探索1 普通に全探索します。 long solve
多次元の std::array を楽に扱う - koturnの日記
はじめに 前回の記事では，多次元の std::vector について書いた． 今回は多次元の std::array について書こうと思う． まず，std::array は組み込み配列と同等の機能を提供するクラスである（というより，組み込み配列のラッパークラスである）． 使用方法としては std::array<int, 4> arr のように，第1テンプレート引数に要素型，第2テンプレート引数に要素数を渡す． std::array<int, 4> arr は int arr[4] に相当する宣言となる． しかし，std::array を多次元にする場合を考えると， std::array<std::array<std::array<int, 30>, 20>, 10> arr; と宣言が長い宣言が必要になる． また，上記の3次元の std::array と同等の組み込み配列は int arr[
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
memset()とmemcpy()
C++でのローカル関数の実現法
