BOJ[백준] - 2262 - 토너먼트 만들기
https://www.acmicpc.net/problem/2262
이 문제는 i ~ j 라는 range가 있다면 그 중간에 k를 두고 i~k 과 k+1 ~ j 로 나누어 최소값이나 최대값을 구하는 류의..
문제들에 속하네요..
비슷한 문제로는 아래와 같은 것들이 있습니다.. 매우 비슷하네요 ㅎㅎ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 |
#include <cstdio>
#define MXN ( 257 )
#define abs(a,b) ((a)>(b) ? (a-b):(b-a))
#define min(a,b) ((a)>(b) ? (b):(a))
int d[MXN][MXN], w[MXN][MXN], a[MXN], n;
int f(int x, int y)
{
if(x == y)
return 0;
if(x + 1 == y)
return (abs(a[x], a[y]));
if(d[x][y])
return d[x][y];
int &ans = d[x][y];
ans = abs(a[x], w[x + 1][y]) + f(x + 1, y);
for(int i = x+1; i < y; i++)
{
ans = min(ans, abs(w[x][i], w[i+1][y]) + f(x, i) + f(i+1, y));
}
return ans;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
{
w[i][i] = a[i];
for(int j = i + 1; j <= n; j++)
w[i][j] = min(w[i][j - 1], a[j]);
}
printf("%d", f(1, n));
return 0;
} |
cs |
'Algorithm 문제풀이 > BOJ [백준] 문제풀이' 카테고리의 다른 글
BOJ[백준] - 1012 - 유기농배추 (0) | 2018.05.19 |
---|---|
BOJ[백준] - 13458 - 시험 감독 (0) | 2017.07.18 |
BOJ[백준] - 1912 - 연속합 (0) | 2017.07.15 |
BOJ[백준] - 1890 - 점프 (0) | 2017.07.15 |
BOJ[백준] - 1720 - 타일 코드 (0) | 2017.07.15 |