2499 의좋은 형제

2499 의좋은 형제 https://www.acmicpc.net/problem/2499

N*N의 수확량이 매겨진 논이 주어진다.
논을 동생 구역, 형 구역으로 나누는데 배분된 구역이 단조 증가하는 계단모양이 되어야한다.
구역을 최대한 공평한 수확량의 차이로 배분하는 방법을 구하는 문제다.

$DP[y][x][young]$ : [y, x]로 구역을 나누고 동생이 young만큼 수확량을 얻을 때 최소 수확량 차이

끝에 도달했을 때 수확량의 차이를 반환해주면 된다.
방법을 구하는 것은 종만북에서도 나오는 reconstruct함수를 구현하면 된다.

#include <cstdio> #include <cstring> #define min(a,b) ((a)<(b)?(a):(b)) #define INF 987654321 inline int abs(int x) { return x < 0 ? -x : x; } int N; int map[21][21]; int sum[21][21], allsum; int dp[21][21][40001]; int solve(int y, int x, int Young) {        //y까지 회색     if (x == N) {         int Old = allsum - Young;         return dp[y][x][Young] = abs(Old - Young);     }       int &ret = dp[y][x][Young];     if (ret != -1) return ret;     ret = INF;     for (int next = y; next >= 0; next--) {         int young = sum[next][x + 1];         ret = min(ret, solve(next, x + 1, young + Young));     }     return ret; } void reconstruct(int y, int x, int Young) {     if (x == N) {         printf("\n");         return;     }     for (int next = y; next >= 0;next--) {         int young = sum[next][x + 1];         if (dp[y][x][Young] == dp[next][x + 1][young + Young]) {             printf("%d ", N - next);             reconstruct(next, x + 1, young + Young);             break;         }     } } int main() {     memset(dp, -1, sizeof dp);     scanf("%d", &N);     for (int n = 1;n <= N;n++)         for (int m = 1;m <= N;m++)             scanf("%d", &map[n][m]);     for (int m = 1;m <= N;m++) {         for (int n = 1;n <= N;n++) {             allsum += map[n][m];             sum[n][m] += sum[n - 1][m] + map[n][m];         }     }     printf("%d\n", solve(N, 0, 0));     reconstruct(N, 0, 0);     return 0; } Colored by Color Scripter

cs