http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1499<\/a><\/p>\nBrief description: <\/h3>\n
\u7565\u3002\uff09<\/p>\n
Analysis: <\/h3>\n
\u5355\u8c03\u961f\u5217 DP\u3002\uff09<\/p>\n
\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int dx[] = {-1, 1, 0, 0};\r\nconst int dy[] = {0, 0, -1, 1};\r\n\r\nconst int N = int(2e2) + 9;\r\nchar Map[N][N]; int dp[2][N][N], p, q, s, t, d;\r\nint n, m;\r\n\r\nvoid gao(int x, int y, int w){\r\n\r\n static PII Q[N]; int cz = 0, op = -1;\r\n\r\n REP(i, w){\r\n if (Map[x][y] == 'x'){\r\n cz = 0, op = -1;\r\n }\r\n else{\r\n while(cz <= op && i - Q[cz].fi > t) ++cz;\r\n while(cz <= op && dp[q][x][y] - i > Q[op].se) --op;\r\n Q[++op] = MP(i, dp[q][x][y] - i);\r\n dp[p][x][y] = Q[cz].se + i;\r\n }\r\n x += dx[d], y += dy[d];\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 int K, x, y; RD(n, m, x, y, K); REP_1(i, n) RS(Map[i]+1);\r\n p = 0, q = 1; FLC(dp[p], 0x80); dp[p][x][y] = 0;\r\n\r\n DO(K){\r\n\r\n swap(p, q); FLC(dp[p], -1); RD(s, t, d); t -= s; ++t; --d;\r\n\r\n if (d == 0){\r\n REP_1(i, m) gao(n, i, n);\r\n }\r\n else if (d == 1){\r\n REP_1(i, m) gao(1, i, n);\r\n } else if (d == 2){\r\n REP_1(i, n) gao(i, m, m);\r\n } else if (d == 3){\r\n REP_1(i, n) gao(i, 1, m);\r\n }\r\n }\r\n\r\n int z = 0; REP_2_1(i, j, n, m) checkMax(z, dp[p][i][j]); OT(z);\r\n}\r\n<\/pre>\nReferences: <\/h3>\n
http:\/\/www.cnblogs.com\/kedebug\/archive\/2013\/02\/28\/2937861.html<\/a><\/p>\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":[22],"tags":[],"class_list":["post-991","post","type-post","status-publish","format-standard","hentry","category-bzoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fZ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/991","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=991"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/991\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=991"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=991"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=991"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}