[BOJ] 2342 Dance Dance Revolution

Time Lapse :33min 57sec

2342.cpp

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
#include <iostream>
using namespace std;
int dp[5][5][100000], n, i;
void init(int val) {
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5; j++)
dp[i][j][val] = 987654321;
}
int getAns(int val) {
int ans = 987654321;
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5; j++)
ans = min(ans, dp[i][j][val]);
return ans;
}
int main() {
init(0);
dp[0][0][0] = 0;
for(i = 0; i < 100001; i++) {
scanf("%d",&n);
if(!n) break;
init(i+1);
for(int l = 0; l < 5; l++)
for(int r = 0; r < 5; r++) {
if(dp[l][r][i] == 987654321) continue;
dp[n][r][i+1] = min(dp[n][r][i+1], dp[l][r][i] + (l == n ? 1 : l == 0 ? 2 : (l&1) == (n&1) ? 4 : 3));
dp[l][n][i+1] = min(dp[l][n][i+1], dp[l][r][i] + (r == n ? 1 : r == 0 ? 2 : (r&1) == (n&1) ? 4 : 3));
}
}
printf("%d",getAns(i));
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/09/03/PS/BOJ/2342/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.