I have ACed this problem 1501. Sense of Beauty. But when I rewrite to beautify my code, it keeps WA in test #7. I don’t know what is wrong in my code. The idea is just simple DP.
Please help me!
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 1002
#define MOD 100000000
#define mp make_pair
int dp[MAXN][MAXN];
int N;
char S[2][MAXN];
char P[2][MAXN];
void to_print(int i, int j) {
if (i == 0 && j == 0)
return;
if (dp[i][j] == 1)
to_print(i - 1, j);
else
to_print(i, j - 1);
printf("%d", dp[i][j]);
}
int main() {
#ifdef OJ
freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);
#endif
scanf("%d\n", &N);
scanf("%s", S[0] + 1);
scanf("%s", S[1] + 1);
for (int i = 1; i <= N; i++) {
P[0][i] = P[0][i - 1] + (S[0][i] == '1');
P[1][i] = P[1][i - 1] + (S[1][i] == '1');
}
dp[1][0] = 1;
dp[0][1] = 2;
for (int i = 2; i <= N; i++) {
if (abs(i - 2 * P[0][i]) > 1)
break;
dp[i][0] = 1;
}
for (int i = 2; i <= N; i++) {
if (abs(i - 2 * P[1][i]) > 1)
break;
dp[0][i] = 2;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int t = i + j;
int n1 = P[0][i] + P[1][j];
if (abs(t - 2 * n1) > 1)
continue;
if (dp[i - 1][j])
dp[i][j] = 1;
else if (dp[i][j - 1])
dp[i][j] = 2;
}
}
if (!dp[N][N])
printf("Impossible\n");
else {
to_print(N, N);
printf("\n");
}
return 0;
}