\u53ea\u8981\u80fd\u5199\u51fa\u66b4\u529b dp \u5c31\u6210\u529f\u4e86 90% \u5566\uff01<\/p>\n
\u4e0d\u59a8\u5148\u628a\u6240\u6709\u70b9\u90fd\u52a0\u8d77\u6765\uff0c\u8003\u8651\u6700\u4f18\u80fd\u901a\u8fc7\u8986\u76d6\u8282\u7701\u591a\u5c11\u3002\u6211\u4eec\u53d1\u73b0\u4e00\u4e2a\u6709\u7528\u7684\u6027\u8d28\u662f\uff0c\u4e09\u89d2\u5f62\u8986\u76d6\u7684\u533a\u57df\uff0c\u662f\u4e0d\u9700\u8981\u91cd\u53e0\u7684\uff0c\u56e0\u6b64\u4f3c\u4e4e\u53ef\u4ee5\u7b80\u5355\u7684 1D\/1D \u52a8\u6001\u89c4\u5212\u3002<\/p>\n
\u8fd9\u91cc\u6211\u4eec\u7528\u6811\u72b6\u6570\u7ec4\uff0c\u53ef\u4ee5\u7ef4\u62a4\u51fa\u4e09\u89d2\u5f62\u8986\u76d6\u533a\u57df\u7684\u4ee3\u4ef7\u3002<\/p>\n
\r\n#include <lastweapon\/io>\r\n#include <lastweapon\/fenwicktree>\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(2e5) + 9;\r\nint n, k, A; vector<PII> P[N]; LL f[N];\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt", "w", stdout);\r\n#endif\r\n\r\n\r\n\tRD(n,k,A); LL z = 0;\r\n\tREP(i ,n) {\r\n\t int x, y, c; RD(x, y, c);\r\n\t z += c; P[k-x].PB({y, c});\r\n\t}\r\n\r\n\tfenwick_tree<int> T(k+1);\r\n\r\n\tREP(i, k+1) {\r\n for (auto p: P[i]) T.add(p.fi, p.se);\r\n checkMax(f[i], (LL)T.sum(0, i+1) - A*i);\r\n REP(j, i) checkMax(f[i], f[j] + T.sum(j+1, i+1) - A*(i-j-1));\r\n\t}\r\n\r\n\tcout << z - f[k] << endl;\r\n}\r\n<\/pre>\n\u8fdb\u4e00\u6b65\u7684\u6211\u4eec\u518d\u628a\u8fd9\u4e2a\u8f6c\u79fb\u5206\u79bb\u5206\u79bb\u653e\u5230\u7ebf\u6bb5\u6811\u91cc\u6c42 rmq \u5c31\u597d\u4e86\u3002<\/p>\n
\r\n#include <lastweapon\/io>\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(2e5) + 9;\r\nconst int NN = 4*N;\r\nint n, k, A; vector<PII> P[N]; int f[N];\r\n\r\nstruct SegTree {\r\n#define lx (x<<1)\r\n#define rx (lx|1)\r\n#define ml ((l+r)>>1)\r\n#define mr (ml+1)\r\n#define lc lx,l,ml\r\n#define rc rx,mr,r\r\n#define rt 1,0,k\r\n\r\n int T[NN], D[NN];\r\n\r\n void add(int x, int d) {\r\n D[x] += d;\r\n T[x] += d;\r\n }\r\n void rls(int x) {\r\n \/\/return;\r\n if (D[x]) {\r\n add(lx, D[x]);\r\n add(rx, D[x]);\r\n D[x] = 0;\r\n }\r\n }\r\n void upd(int x) {\r\n T[x] = max(T[lx], T[rx]);\r\n }\r\n void Build(int x, int l, int r) {\r\n if (l == r) {\r\n T[x] = A*l;\r\n } else {\r\n Build(lc);\r\n Build(rc);\r\n upd(x);\r\n }\r\n }\r\n\r\n int Add(int x, int l, int r, const int p, const int d) {\r\n if (l == r) {\r\n T[x] += d;\r\n } else {\r\n rls(x);\r\n if (p < mr) Add(lc, p, d);\r\n else Add(rc, p, d);\r\n upd(x);\r\n }\r\n }\r\n\r\n void Add(int x, int l, int r, const int a, const int b, const int d) {\r\n if (b < l || r < a) return;\r\n if (a <= l && r <= b) {\r\n add(x, d);\r\n } else {\r\n rls(x);\r\n Add(lc, a, b, d);\r\n Add(rc, a, b, d);\r\n upd(x);\r\n }\r\n }\r\n\r\n int Query(int x, int l, int r, const int a, const int b) {\r\n if (b < l || r < a) return 0;\r\n if (a <= l && r <= b) {\r\n return T[x];\r\n } else {\r\n rls(x);\r\n return max(Query(lc, a, b), Query(rc, a, b));\r\n }\r\n }\r\n} T;\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt", "w", stdout);\r\n#endif\r\n\r\n\r\n\tRD(n,k,A); int z = 0; REP(i, n) {\r\n\t int x, y, c; RD(x, y, c); z += c;\r\n\t P[k-x].PB({y, c});\r\n\t}\r\n\r\n\tT.Build(rt);\r\n\r\n\tREP(i, k+1) {\r\n\t if (i) T.Add(rt, i, f[i-1]);\r\n for (auto p: P[i]) T.Add(rt, 0, p.fi, p.se);\r\n checkMax(f[i], T.Query(rt, 0, i) - A*i);\r\n\t}\r\n\r\n\tcout << z - f[k] << endl;\r\n}\r\n\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Problem E. Tenzing and Triangle \u53ea\u8981\u80fd\u5199\u51fa\u66b4\u529b dp \u5c31\u6210\u529f\u4e86 90% \u5566\uff01 \u4e0d\u59a8\u5148\u628a\u6240\u6709\u70b9\u90fd\u52a0\u8d77\u6765\uff0c\u8003\u8651\u6700\u4f18\u80fd\u901a\u8fc7\u8986\u76d6\u8282\u7701\u591a\u5c11\u3002\u6211\u4eec\u53d1\u73b0\u4e00\u4e2a\u6709\u7528\u7684\u6027\u8d28\u662f\uff0c\u4e09\u89d2\u5f62\u8986\u76d6\u7684\u533a\u57df\uff0c\u662f\u4e0d\u9700\u8981\u91cd\u53e0\u7684\uff0c\u56e0\u6b64\u4f3c\u4e4e\u53ef\u4ee5\u7b80\u5355\u7684 1D\/1D \u52a8\u6001\u89c4\u5212\u3002 \u8fd9\u91cc\u6211\u4eec\u7528\u6811\u72b6\u6570\u7ec4\uff0c\u53ef\u4ee5\u7ef4\u62a4\u51fa\u4e09\u89d2\u5f62\u8986\u76d6\u533a\u57df\u7684\u4ee3\u4ef7\u3002 #include <lastweapon\/io> #include <lastweapon\/fenwicktree> using namespace lastweapon; const int N = int(2e5) + 9; int n, k, A; vector<PII> P[N]; LL f[N]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); \/\/freopen("\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt", "w", stdout); #endif RD(n,k,A); LL z = 0; REP(i ,n) […]<\/p>\n","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-3057","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Nj","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3057","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=3057"}],"version-history":[{"count":4,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3057\/revisions"}],"predecessor-version":[{"id":3062,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3057\/revisions\/3062"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3057"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3057"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}