第11回情オリ本選対策3日目
- アリ本の個数制限部分和の問題よく分からん。
- 最長部分増加列覚えた。が、O(n log n)解法は直感的理解はできていないので、応用させられると死ぬ可能性がある。
- 分割数と重複組合せの話は理解するのが面倒そうなので飛ばした。
- Union-Find多分書けるけど一度も手で実装した事ないから今度食物連鎖一度解こう。
- Segment木の冒頭をちょろっと読んだ所で集中力がプッツンしたので寝る
あとダラダラ起きてないでちゃんと寝ろ俺
書いた物
- ビルの飾りつけ(2007年度JOI春合宿)
#include <cstdio> #include <vector> #include <climits> #include <algorithm> using namespace std; int main() { int n; scanf("%d\n", &n); vector<int> bldgs(n), dp(n, INT_MAX); for (int i = 0 ; i < n; ++i) scanf("%d\n", &bldgs[i]); for (int i = 0; i < bldgs.size(); ++i) *(lower_bound(dp.begin(), dp.end(), bldgs[i])) = bldgs[i]; int res = 1; for (int i = 0; i < dp.size(); ++i) { if (dp[i] == INT_MAX) continue; res = i + 1; } printf("%d\n", res); return 0; }
- AOJ0157 Russian Dolls
#include <cstdio> #include <vector> #include <algorithm> #include <map> using namespace std; int main() { int n; while (scanf("%d\n", &n), n) { map<int, vector<int> > dollsInput; for (int i = 0; i < n; ++i) { int h, r; scanf("%d %d\n", &h, &r); dollsInput[h].push_back(r); } int m; scanf("%d\n", &m); for (int i = 0; i < m; ++i) { int h, r; scanf("%d %d\n", &h, &r); dollsInput[h].push_back(r); } vector<vector<int> > dolls; dolls.reserve(dollsInput.size()); unsigned int maxSameHeight = 0; for (map<int, vector<int> >::iterator it = dollsInput.begin(); it != dollsInput.end(); ++it) { dolls.push_back((*it).second); sort(dolls.back().begin(), dolls.back().end()); maxSameHeight = max(maxSameHeight, dolls.back().size()); } vector<vector<int> > dp(dolls.size(), vector<int>(maxSameHeight)); int res = 0; for (int i = 0; i < dp.size(); ++i) for (int j = 0; j < dp[i].size(); ++j) { int cur = 1; for (int x = 0; x < i; ++x) for (int y = 0; y < dolls[x].size(); ++y) { if (dolls[x][y] < dolls[i][j]) { cur = max(cur, dp[x][y] + 1); } } dp[i][j] = cur; res = max(res, cur); } printf("%d\n", res); } return 0; }
何故、WAするんだ、誰か教えてー!(他力本願)
追記:よくあるWAだときゅうりに教えてもらったが実はよく分かっていないので、あとで確認する