第11回情オリ本選対策12日目(あと使えるのは3日!)
今日やるつもりの物
- アリ本P126の少し考察を要するDP5問、P.253のビットDP5問
- AOJ0550 Dividing Snacksをどうにか他人の見てでも
- JOI Flagもどうにか
- POJ3280 Cheapest Palindromeもどうにか
- AOJ0232 Life Gameもどうにか
- AOJ1056 Ben Tohもどうにか解説みて
- 解きたきゃ解く物3問
17:00-21:50
- POJ 1065 Wooden Sticks、他人の解見たけどあんまりDPに見えないというか他人の解がDPに見えないのでパス。よく分からないし。
- サクサク進まねぇなぁ…生まれてはじめてSegment Tree書いたので、Range Maximum Queryの正しく動くか不明な物をおいておきますね つ
#include <cstdio> #include <vector> using namespace std; class RMQ { private: int n; vector<int> data; public: RMQ(int n) { int t = 1; while (t < n) t *= 2; data = vector<int>(t * 2 - 1, 0); this->n = t; return; } void set(int idx, int value) { int k = idx + n - 1; data[k] = value; while (k > 0) { k = (k - 1) / 2; data[k] = max(data[k * 2 + 1], data[k * 2 + 2]); } return; } int query_impl(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return data[k]; return max( query_impl(a, b, k * 2 + 1, l, (l + r) / 2), query_impl(a, b, k * 2 + 1, (l + r) / 2, r)); } int query(int a, int b) { return query_impl(a, b, 0, 0, n); } };
- POJ1631 Bridging signals、ただのLISだが、最初気付かずぐぐってもLIS解法ではないのが上のほうに出てきていたので、なんとなくRMQを書いてしまったの図が↑。ちゃんと問題文読解しよう。あとLISのO(n log n)解法覚えてませんでしたが多分これで覚えた。
#include <cstdio> #include <vector> #include <algorithm> #include <climits> using namespace std; int main() { int n; scanf("%d\n", &n); for (int h = 0; h < n; ++h) { int p; scanf("%d\n", &p); vector<int> routes(p); for (int i = 0; i < p; ++i) scanf("%d\n", &routes[i]); vector<int> dp(p, INT_MAX); for (int i = 0; i < p; ++i) { *(lower_bound(dp.begin(), dp.end(), routes[i])) = routes[i]; } int res = p - 1; for (int i = 0; i < p; ++i) { if (dp[i] == INT_MAX) { res = i; break; } } printf("%d\n", res); } return 0; }
- POJ3666、わからん!わからん!
- POJ 2392 Space Elevator、ソートしてからDPというのがありえん程苦手である。数学センス皆無よろしく、脳内で証明を立てて(反例がない確信を得て)何かするのが極めて苦手。ソートさえすれば普通のDP。
#include <cstdio> #include <vector> #include <algorithm> using namespace std; class Block { public: int h, a, c; Block(int h, int a, int c) : h(h), a(a), c(c) {} bool operator<(const Block& bl) const { return a < bl.a; } }; int main() { int K; scanf("%d\n", &K); vector<Block> blocks; blocks.reserve(K); for (int i = 0; i < K; ++i) { int h, a, c; scanf("%d %d %d\n", &h, &a, &c); blocks.push_back(Block(h, a, c)); } sort(blocks.begin(), blocks.end()); vector<vector<bool> > dp(2, vector<bool>(blocks.back().a + 1, false)); int cur = 0, prev = 1; dp[prev][0] = true; int res = 0; for (int i = 0; i < K; ++i) { for (int j = 0; j < dp[cur].size(); ++j) { if (!dp[prev][j]) continue; for (int k = j, l = min(j + blocks[i].h * blocks[i].c, blocks[i].a); k <= l; k += blocks[i].h) { dp[cur][k] = true; res = max(res, k); } } cur = !cur, prev = !prev; } printf("%d\n", res); return 0; }
- POJ 2184 分かるはずなんだけど写経モードに入ってしまい、ためにならない上に答えあわないのでパス。
- POJ 2441 メモ化で書いてMLEったのでDPに落としたらサンプルケース通らなくなった時の脱力感について