鉄則本★5
LIS。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 長さ の数列 の LIS の長さを求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; const int INF = 1 << 29; int main() { int N, res = 0; cin >> N; vector<int> A(N); for (int i = 0; i < N; </int></bits/stdc++.h>…
dp[どこまで見たか][ビット] というタイプのビット DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは 0 または 1 である。いくつかの行を選んで、次の条件を満たすようにしたい。選ぶべき行数の最小値を求め…
半分全列挙の典型問題! 問題へのリンク 問題概要 長さが の 4 つの数列が与えられる。これらから要素を 1 個ずつとってきて、総和を にすることが可能か判定せよ。 制約 メモ 「半分全列挙」を用いる。詳細は鉄則本にて。 コード #include <bits/stdc++.h> using namespace</bits/stdc++.h>…
セグメント木や BIT の最初の練習問題によさそうな問題 問題へのリンク 問題概要 長さ の数列 がある。最初はすべての要素が 0 となっている。この数列に対して、以下の 2 種類のクエリに答えよ ( 個のクエリが与えられる)。 クエリ 1: が与えられるので、 …
セグメント木の最初の練習問題によさそうな問題 問題へのリンク 問題概要 長さ の数列 がある。最初はすべての要素が 0 となっている。この数列に対して、以下の 2 種類のクエリに答えよ ( 個のクエリが与えられる)。 クエリ 1: が与えられるので、 の値を …