이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <time.h>
using namespace std;
char a[1000005];
char b[1000005];
bool have[15][1000005]={0};
int DP[15][1000005],N;
bool vis[1000005]={0};
queue < pair < int , int > > BFS;
int F(int what,int here)
{
if(here==N) return 0;
if(have[what][here]) return DP[what][here];
DP[what][here]=2e9;
have[what][here]=1;
if(a[here]==b[here]) DP[what][here]=min(DP[what][here],F(0,here+1));
if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1)+1);
if(b[here]=='1')
{
DP[what][here]=min(DP[what][here],F(3,here+1)+2);
DP[what][here]=min(DP[what][here],F(5,here+1)+1);
DP[what][here]=min(DP[what][here],F(6,here+1)+2);
DP[what][here]=min(DP[what][here],F(9,here+1)+2);
}
else
{
DP[what][here]=min(DP[what][here],F(2,here+1)+2);
DP[what][here]=min(DP[what][here],F(4,here+1)+1);
DP[what][here]=min(DP[what][here],F(7,here+1)+2);
DP[what][here]=min(DP[what][here],F(8,here+1)+2);
}
if(what==1)
{
if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
else
{
if(b[here]=='1') DP[what][here]=min(DP[what][here],F(6,here+1)+1);
else DP[what][here]=min(DP[what][here],F(7,here+1)+2);
}
}
if(what==2)
{
if(b[here]=='1')
{
DP[what][here]=min(DP[what][here],F(5,here+1));
DP[what][here]=min(DP[what][here],F(6,here+1)+1);
}
else DP[what][here]=min(DP[what][here],F(2,here+1));
}
if(what==3)
{
if(b[here]=='0')
{
DP[what][here]=min(DP[what][here],F(4,here+1));
DP[what][here]=min(DP[what][here],F(7,here+1)+1);
}
else DP[what][here]=min(DP[what][here],F(3,here+1));
}
if(what==4)
{
if(b[here]=='1')
{
DP[what][here]=min(DP[what][here],F(3,here+1)+1);
DP[what][here]=min(DP[what][here],F(9,here+1)+1);
}
else DP[what][here]=min(DP[what][here],F(4,here+1));
}
if(what==5)
{
if(b[here]=='0')
{
DP[what][here]=min(DP[what][here],F(2,here+1)+1);
DP[what][here]=min(DP[what][here],F(8,here+1)+1);
}
else DP[what][here]=min(DP[what][here],F(5,here+1));
}
if(what==6)
{
if(b[here]=='0')
{
DP[what][here]=min(DP[what][here],F(8,here+1)+1);
DP[what][here]=min(DP[what][here],F(2,here+1)+1);
if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
}
else DP[what][here]=min(DP[what][here],F(6,here+1));
}
if(what==7)
{
if(b[here]=='1')
{
DP[what][here]=min(DP[what][here],F(9,here+1)+1);
DP[what][here]=min(DP[what][here],F(3,here+1)+1);
if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
}
else DP[what][here]=min(DP[what][here],F(7,here+1));
}
if(what==8)
{
if(b[here]=='1')
{
DP[what][here]=min(DP[what][here],F(9,here+1)+1);
DP[what][here]=min(DP[what][here],F(3,here+1)+1);
DP[what][here]=min(DP[what][here],F(5,here+1));
}
else DP[what][here]=min(DP[what][here],F(8,here+1));
}
if(what==9)
{
if(b[here]=='0')
{
DP[what][here]=min(DP[what][here],F(8,here+1)+1);
DP[what][here]=min(DP[what][here],F(2,here+1)+1);
DP[what][here]=min(DP[what][here],F(4,here+1));
}
else DP[what][here]=min(DP[what][here],F(9,here+1));
}
return DP[what][here];
}
int main()
{
//srand(time(NULL));
int M,ans=0,i,j,x=0,y=0,aa,tt;
scanf("%d",&N);
scanf("%s %s",a,b);
printf("%d\n",F(0,0));
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
lamp.cpp: In function 'int main()':
lamp.cpp:129:9: warning: unused variable 'M' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^
lamp.cpp:129:11: warning: unused variable 'ans' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^~~
lamp.cpp:129:17: warning: unused variable 'i' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^
lamp.cpp:129:19: warning: unused variable 'j' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^
lamp.cpp:129:21: warning: unused variable 'x' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^
lamp.cpp:129:25: warning: unused variable 'y' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^
lamp.cpp:129:29: warning: unused variable 'aa' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^~
lamp.cpp:129:32: warning: unused variable 'tt' [-Wunused-variable]
129 | int M,ans=0,i,j,x=0,y=0,aa,tt;
| ^~
lamp.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
lamp.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
131 | scanf("%s %s",a,b);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |