{"id":1043,"date":"2014-10-19T22:12:16","date_gmt":"2014-10-19T14:12:16","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1043"},"modified":"2014-10-19T22:12:16","modified_gmt":"2014-10-19T14:12:16","slug":"bzoj-1597-usaco2008-mar%e5%9c%9f%e5%9c%b0%e8%b4%ad%e4%b9%b0","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1597-usaco2008-mar%e5%9c%9f%e5%9c%b0%e8%b4%ad%e4%b9%b0\/","title":{"rendered":"BZOJ 1597. [Usaco2008 Mar]\u571f\u5730\u8d2d\u4e70"},"content":{"rendered":"

<\/p>\n

Brief description: <\/h3>\n

\u7565\u3002\uff09<\/p>\n

Analysis: <\/h3>\n

\"1\"<\/a><\/p>\n

\r\nconst int N = int(5e4) + 9;\r\n\r\nVII II, I; LL f[N]; int q[N], cz, op;\r\nint n;\r\n\r\n#define k I[i].fi\r\n#define x(j) I[j+1].se\r\n#define y(j) f[j]\r\n#define eval(j) ((LL)k*x(j)+y(j))\r\n\r\nLL det(LL x1, LL y1, LL x2, LL y2){\r\n    return x1*y2 - x2*y1;\r\n}\r\n\r\nint dett(int p0, int p1, int p2){\r\n    LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0));\r\n    return t < 0 ? -1 : t > 0;\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    II.resize(RD(n)); REP(i, n) RD(II[i].fi, II[i].se);\r\n\r\n    SRT(II); II.PB(MP(INF, 0)); I.PB(MP(0, INF)); REP(i, n){\r\n        while (I.back().se <= II[i].se) I.pop_back();\r\n        I.PB(II[i]);\r\n    }\r\n\r\n    \/*n = SZ(I)-1; REP_1(i, n){\r\n        f[i] = INFF;\r\n        REP(j, i) checkMin(f[i], (LL)I[i].fi*I[j+1].se + f[j]);\r\n        cout << f[i] << endl;\r\n    }*\/\r\n\r\n    n = SZ(I)-1; cz = 0, op = 0; REP_1(i, n){\r\n        while (cz < op && eval(q[cz]) >= eval(q[cz+1])) ++cz; f[i] = eval(q[cz]);\r\n        while (cz < op && dett(q[op-1], q[op], i) > 0) --op; q[++op] = i;\r\n        \/\/cout << f[i] << endl;\r\n    }\r\n\r\n    cout << f[n] << endl;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1043","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-gP","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1043","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1043"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1043\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1043"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1043"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1043"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}