Submission #132553

#TimeUsernameProblemLanguageResultExecution timeMemory
132553MrTEKLamps (JOI19_lamps)C++14
0 / 100
10 ms4472 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair <int,int> ii;

const int N = 2e3 + 5;
const int inf = 2e9;
const int SQ = 300;

int n,d[2][N][N],dp[N][2];
char a[2][N],b[N];

int f(int cur,int w) {
	if (cur == n + 1)
		return 0;
	int &res = dp[cur][w];
	if (res != -1)
		return res;
	res = 1e9;
	for (int i = cur ; i <= n ; i++)
		res = min(res,d[w][cur][i] +  f(i + 1,!w));
	return res += (w == 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; cout.tie(NULL);
	cin >> n >> (a[0] + 1) >> (b + 1);
	for (int i = 1 ; i <= n ; i++)
		a[1][i] = !(a[0][i] - '0') + '0';
	for (int w = 0 ; w < 2 ; w++) {
		for (int i = n ; i >= 1 ; i--) {
			int j = i;
			while(j + 1 <= n && b[j + 1] == b[i])
				j++;
			int flag = 0;
			for (int k = i ; k <= j ; k++) {
				if (a[w][k] != b[k])
					flag = 1;
				d[w][i][k] = flag;
			}
			for (int k = j + 1 ; k <= n ; k++)
				d[w][i][k] = d[w][i][j] + d[w][j + 1][k];
		}
	}
	memset(dp,-1,sizeof dp);
	cout << min(f(1,0),f(1,1)) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...