#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int>vec[20];
int cost[15][15];
int calc(int current, int target){
if(cost[current][target]!=-1)
return cost[current][target];
vector<int>X=vec[current];
vector<int>Y=vec[target];
int m = X.size();
int n = Y.size();
int L[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
return cost[current][target]=L[m][n];
}
int main()
{
memset(cost,-1,sizeof(cost));
int n;
string a,b;
cin>>n>>a>>b;
for(char&ch:a)ch-='0';
for(char&ch:b)ch-='0';
map<vector<int>,int>ind{};
vector<int>vmsk[20];
int mask[20];
int to[2][20];
int cur=0;
for(int i = 0; i < 8; i++){
vector<int>v;
int msk=0;
for(int j = 0; j < 3; j++){
if(i&(1<<j))v.push_back(j),msk+=(1<<j);
}
vmsk[msk]=v;
do{
vec[cur]=v;
ind[v]=cur;
mask[cur]=msk;
++cur;
}while(next_permutation(v.begin(),v.end()));
}
int dp[15][n+1];
for(int i = 0; i < 15; i++){
for(int j = 0; j < n + 1; j++){
dp[i][j]=1e6+1;
}
}
for(int i = 0; i < 15; i++){
int val = a[0];
for(int x : vec[i]){
if(x==0)val=0;
else if(x==1)val=1;
else val ^= 1;
}
if(val==b[0]){
dp[i][0]=vec[i].size();
//assert(vec[i].size());
}
to[a[0]][i]=val;
val=a[0]^1;
for(int x : vec[i]){
if(x==0)val=0;
else if(x==1)val=1;
else val ^= 1;
}
to[a[0]^1][i]=val;
}
/*for(int i = 0; i < n; i++){
for(int j = 0; j < cur; j++){
assert(dp[j][i]);
}
}*/
for(int i = 0; i + 1 < n; i++){
for(int j = 0; j < 15; j++){
for(int k = 0; k < 15; k++){
if(to[a[i+1]][k]==b[i+1])
dp[k][i+1]=min(dp[k][i+1],dp[j][i]+calc(j,k));
}
}
}
int ans = 1e9;
for(int j = 0; j < 15; j++){
ans=min(ans,dp[j][n-1]);
}
cout<<ans;
return 0;
}
Compilation message
lamp.cpp: In function 'int main()':
lamp.cpp:73:16: warning: array subscript has type 'char' [-Wchar-subscripts]
73 | to[a[0]][i]=val;
| ^
lamp.cpp:90:29: warning: array subscript has type 'char' [-Wchar-subscripts]
90 | if(to[a[i+1]][k]==b[i+1])
| ^
lamp.cpp:39:9: warning: variable 'mask' set but not used [-Wunused-but-set-variable]
39 | int mask[20];
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
