https://www.acmicpc.net/problem/14722
초코우유부터 마실 수 있으므로 뒤에서부터 생각하기보다 앞에서 생각이 편한 것 같다.
memo[x][y][k] = 현재 k 우유를 마실 차례일 때 x,y 에서 부터 마실 수 있는 최대 수
각 상태에서 k 우유를 마실 수도, 안마실 수도 있다.
memo[x][y][k] = max(
f(x+1, y, k),
f(x, y+1, k),
f(x+1, y, k next) + 1,
f(x, y+1, k next) + 1
) if (k == map[x][y])
memo[x][y][k] = max(
f(x+1, y, k),
f(x, y+1, k),
} if (k != map[x][y])
https://www.acmicpc.net/problem/2156
현재 포도주를 선택할 수 있는 경우와 선택하지 않는 경우(중요)가 있을 수 있다
d[n] = max(d[n-3] + d[n-1] + arr[n],
d[n-2] + arr[n],
d[n-1] // 선택하지 않는경우
)
2차원 배열로 접근가능하다
d[n][k]: n 번째 포도주 차례에서 k번째로 시식하는 경우의 최대 합
k = 0: 아무것도 먹지 않은 경우
k = 1: 첫번째 시식한 경우
k = 2: 두번째 시식한 경우
d[n][1] = d[n-1][0] + arr[n]
d[n][2] = d[n-1][1] + arr[n]
d[n][0] = ??
d[n-1][2] 라고 생각 할 수 있으나, 현재 안마실 때의 최대 합은
max(d[n-1][0], d[n-1][1], d[n-1][2]) 이다
memo[1][0] = 0;
memo[1][1] = arr[1];
memo[1][2] = 0;
int ans = arr[1];
for (int i = 2; i <= N; i++) {
memo[i][1] = memo[i-1][0] + arr[i];
memo[i][2] = memo[i-1][1] + arr[i];
memo[i][0] = Math.max(Math.max(memo[i-1][1], memo[i-1][2]), memo[i-1][0]) ;
ans = Math.max(memo[i][0], memo[i][1]);
ans = Math.max(ans, memo[i][2]);
}
System.out.println(ans);
https://www.acmicpc.net/problem/1626
개선이 필요
MST가 아닌 edge 중, ST 가 되도록 다른 edge를 끊어본다
가령 edge 14를 연결하면 cycle이 생기고, 이때 어느 edge를 제거해도 ST가 된다
이때 가장 큰 edge를 제거하는게 두번째 MST를 얻을 수 있다.
추가하려는 14길이의 edge node의 a, b 구간 (12->4) 중 트리에서 가장 긴 구간을 찾는다면, 이진탐색(lca)으로 12을 찾을 수 있다
https://www.acmicpc.net/problem/1513
d[x][y][c]: x,y에 왔을 때 총 들린 오락실 수가 c일 때의 총 경우의 수로 부분 정의
오락실이 증가하는 방향이어야 하므로 상태가 하나 더 필요
d[x][y][k][c]: x,y에 왔을 때 이전 들린 오락실이 k이고, 총 들린 오락실 수가 c일 때의 총 경우의 수로 부분 정의
// d[i][j][k][c] += d[i-1][j][k][c-1] + d[i][j-1][k][c-1];
f(x, y, k, c) =
f(x - 1, y, k, i) + f(x, y - 1, k, i) // 1 <= i <= C, if x=y is not game room
f(x - 1, y, j, i - 1) + f(x, y - 1, j, i - 1) // 1 <= i <= C, 0 <= j < game room, if x=y is game room
상향식
for (int i=0; i<=C; i++) {
for (int k=0; k < max(C,1); k++) {
ans[i] += d[N][M][k][i];
ans[i] %= mod;
}
printf("%d ",ans[i]);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (game[i][j] == -1) { //오락실이 아니고 하나도 안들린경우
d[i][j][0][0] += d[i-1][j][0][0] + d[i][j-1][0][0];
d[i][j][0][0] %= mod;
}
// 오락실 c개 들리는 경우
for (int c = 1; c <= C; c++) {
int gameNum = game[i][j];
if (gameNum == -1) {
// 오락실이 아니면 방문한 오락실들 확인
for (int k = 0; k <= C; k++) {
d[i][j][k][c] += d[i-1][j][k][c] + d[i][j-1][k][c];
}
} else {
if (c == 1) {
// 현위치가 오락실이고 처음방문하는 경우라면
// 이전 오락실은 0, 이전 방문 총 오락실 수 0
d[i][j][0][c] += d[i-1][j][0][0] + d[i][j-1][0][0];
} else {
for (int k = 0; k < gameNum; k++) {
d[i][j][k][c] += d[i-1][j][k][c-1] + d[i][j-1][k][c-1];
}
}
}
}
}
}
하향식
for (int i = 0; i <= c; i++) {
int ans = 0;
for (int j = 0; j <= c; j++) {
ans = f(n, m, j, i);
}
sysout(ans)
}
int f(int n int m, int k, int c) {
if (n < 1 || n > N || m < 1 || m > M) {
return 0;
}
int ret = d[n][m][k][c];
if (ret != -1) {
return ret;
}
int roomNum = game[n][m];
if (roomNum == 0) {
// 오락실이 아니면 이전과 상태변화가 없다
ret = f(n-1, m, k, c) + f(n, m-1, k, c);
} else {
if (roomNum == k) {
for (int i = 0; i < k; i++) {
// 이전은 k 보다 적어야된다
ret = f(n-1, m, i, c - 1) + f(n, m-1, i, c - 1);
}
}
}
return r;
}