์ ๋ฒ์ฃผ ABC์์ E
๋ฒ์ 1๋ถ์ฐจ๋ก ์ ์ถ ๋ชปํ ์ดํ๋ก ๋ ๊ณ ์ง๋ณ(๊ฒฝ๊ณ์ ์ ๋ชป๋๋ ๋ณ)์ด ๋์ง๋ ํ๋๋ฐ, ๋คํํ ๊ทธ๋ฆฐ์ ์์ฐฉํ๋ค.
A | B | C | D | E | F | G |
---|---|---|---|---|---|---|
AC | AC | AC | AC | AC | - | - |
C
์์ upper_bound
์ฌ์ฉ์ end
check๋ฅผ ํ์ง ์์์ 3ํ์ ํ๋ค. CPH
๊ฐ ๊ฐ์๊ธฐ ๋์ํ์ง ์์์ ์ข ๋ฉ๋ถ์ด์๋๋ฐ, ๊ทธ๋ฐ๊ฑฐ ์น๊ณ ์ ์ณค๋ค๋ ๊ฐ์ธ์ ์ธ ํ๊ฐ.
ํ๋ฃจ ๋ค์ ๋ ์ง๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ . ๋ค์ ๋ฌ๋ก ๋์ด๊ฐ๋ case, ๋ค์ ํด๋ก ๋์ด๊ฐ๋ case ๋ชจ๋ ๋นผ๋จน์ง ๋ง์์ผ ํ๋ค.
์ ํด๋ ์ ๋ธ๋ฃจํธํฌ์ค. ๋๋ ์๋ ํํ์ DP
๋ก ํ์๋ค. (Knapsack)
int dp[200];memset(dp, 0x3F, sizeof(int) * 200);dp[0] = 0;for(int i = 1; i <= 6; ++i) dp[i] = S;for(int i = 6; i <= 100; ++i) {if (i >= 6) {dp[i] = min(dp[i], dp[i - 6] + S);}if (i >= 8) {dp[i] = min(dp[i], dp[i - 8] + M);}if (i >= 12) {dp[i] = min(dp[i], dp[i - 12] + L);}}int ans = 0x7FFFFFFF;for(int i = N; i <= N + 12; ++i) {if (dp[i] < ans) ans = dp[i];}printf("%d\n", ans);
์ฌ๊ธฐ์ ๊ตฌํ ์ด์๋ก 3ํ์ ํ๋ค. upper_bound
์์ ๊ฒฐ๊ณผ๊ฐ ์์ผ๋ฉด, end()
iterator๋ก ์์นํ๊ณ , ์ฌ๊ธฐ์๋ ์ฐ๋ ๊ธฐ๊ฐ์ด ๋ค์ด๊ฐ ์์์ ์ ์ํ๋๋ก ํ์.
์ ํด๋ 2์ฐจ์ Prefix Sum
+ Case work ์๋ค. ๋๋ 2D Fenwick
์ผ๋ก ์ฒ๋ฆฌํ๋ค. ๊ทธ๋ ์ง๋ง ์ค๊ฐ์ board๊ฐ ์
๋ฐ์ดํธ ๋๋ ์ฟผ๋ฆฌ๊ฐ ์๊ธฐ ๋๋ฌธ์ ์ ํด๊ฐ ๋ ์ข์๋ณด์ธ๋ค. ํ์ผ์ด ๋ฐ๋ณต๋๋ค๋ ๊ฒ์ด ๊ตฌํ์ ๋ณต์กํ๊ฒ ๋ง๋ค์๋ค. ๋ฐ์ ธ์ผํ ์ผ์ด์ค๊ฐ ๋ง๊ธฐ ๋๋ฌธ์, D
๋ฅผ ๊ฑด๋๋ด ์ฌ๋๋ค๋ ๋ง์ด ๋ณด์๊ณ , ๊ฒฐ๋ก ๋ง ๋๊ณ ๋ณด๋ฉด D
ํ ์๊ฐ์ E
์ F
๋ฅผ ํธ๋ ๊ฒ์ด ์ ๋ฐฐ ์๋ ๊ฒ ๊ฐ๋ค. ๋คํํ ์๊ฐ ๋ด์ AC
๋ฅผ ๋ฐ์์ ๋คํ์ด์ง๋ง, ๋ง์ฝ ๊ตฌํํ๋ค๊ฐ ์๊ฐ์ ์ด๊ณผํ๋ค๋ฉด ์ ๋ฒ์ฃผ์ ์
๋ชฝ์ด ๋ํ์ด ๋์์ ๋ฏ..
๊ฐ์ธ์ ์ผ๋ก๋ ๊ตฌํ ์ฐ์ต์ ์๋นํ ๋์์ด ๋๋ ๋ฌธ์ ์๋ค๊ณ ์๊ฐํ๋ค. ๋ค์์ ๋น์ทํ ์ ํ์ด ๋์ค๋ฉด ์ข ๋ ๋นจ๋ฆฌ ํ ์ ์์ง ์์๊น..
์ ํด๋ ์ด๊ฒ์ ๊ฒ ์ฒดํฌํ๋ฉด์ ์๊ฐ๋ณต์ก๋๋ฅผ ๋ง์ด ์ค์ธ ๊ฒ์ผ๋ก ๋ณด์ด๋๋ฐ(), ๋๋ ๊ทธ๋ฅ ๋ฒ ์ด์ค ์๋ฃจ์ ์ ์ ๋ ฌ ํ ์ ๋นํ ์ปคํ ์ ๋ถ์ฌ์ ํต๊ณผ์์ผฐ๊ณ , ์ด ๋ฐฉ๋ฒ์ด ๋ ๊ฐ๋จํ๋ฏ ํ๋ค. ๋ธ๋ฃจํธํฌ์ค๋ก ์ ๋ ๋๋ ์๋ฃจ์ ์ ๊ฒฝ์ฐ์๋ ์ฃผ๋ก ์ปคํ ์ ํ๋ฉด ์๊ฐ ๋ด์ ์ ๋ค์ด์ค๋ ๊ฒ ๊ฐ๋ค.
Segment Tree๋ฅผ ํ์ฉํด์ ํ ์ ์๋ค๊ณ ํ๋ค. ์ถํ ๋ค์ ํ์ด๋ณผ ์์ .
Skip