BOJ[백준] - 2262 - 토너먼트 만들기

Posted by ceyx
2017. 7. 30. 19:20 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/2262

 

 

이 문제는 i ~ j  라는 range가 있다면 그 중간에 k를 두고 i~k 과 k+1 ~ j 로 나누어 최소값이나 최대값을 구하는 류의..

문제들에 속하네요..

 

 

비슷한 문제로는 아래와 같은 것들이 있습니다.. 매우 비슷하네요 ㅎㅎ

BOJ[백준] - 11066 - 파일합치기

BOJ[백준] - 11049 - 행렬 곱셈 순서

 

 

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