Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#624#113. 【0621 模拟赛】Zrinkataccat1001989ms394688kbC++14751b2025-06-21 15:01:442025-06-21 23:50:04

answer

#include<bits/stdc++.h>
#define ll   long long
const ll N=5e3;
using namespace std;
ll n,m,a[N+5],b[N+5],dp[N+5][N+5][2];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i][0][a[i]]=dp[i-1][0][a[i-1]]+(a[i]==a[i-1]);
		dp[i][0][!a[i]]=0x3f3f3f3f3f3f3f3f;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>b[i];
		dp[0][i][b[i]]=dp[0][i-1][b[i-1]]+(b[i]==b[i-1]);
		dp[0][i][!b[i]]=0x3f3f3f3f3f3f3f3f;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<=1;k++){
				dp[i][j][k]=min(a[i]==k?min(dp[i-1][j][(bool)k]+1,dp[i-1][j][!(bool)k]):0x3f3f3f3f3f3f3f3f,b[j]==k?min(dp[i][j-1][(bool)k]+1,dp[i][j-1][!(bool)k]):0x3f3f3f3f3f3f3f3f);
			}
		}
	}
	cout<<n+m+min(dp[n][m][1],dp[n][m][0]);
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 1ms
memory: 3168kb

input:

0
500 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 ...

output:

750

result:

ok "750"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3296kb

input:

0
500 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 ...

output:

737

result:

ok "737"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

0
500 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 ...

output:

756

result:

ok "756"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

0
500 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 ...

output:

745

result:

ok "745"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3292kb

input:

0
500 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 ...

output:

738

result:

ok "738"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3340kb

input:

0
500 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 ...

output:

753

result:

ok "753"

Subtask #2:

score: 20
Accepted

Test #7:

score: 20
Accepted
time: 1ms
memory: 42580kb

input:

500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1490

result:

ok "1490"

Test #8:

score: 0
Accepted
time: 1ms
memory: 42576kb

input:

500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1468

result:

ok "1468"

Test #9:

score: 0
Accepted
time: 1ms
memory: 42652kb

input:

500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1516

result:

ok "1516"

Test #10:

score: 0
Accepted
time: 2ms
memory: 42540kb

input:

500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1502

result:

ok "1502"

Test #11:

score: 0
Accepted
time: 0ms
memory: 42448kb

input:

500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1484

result:

ok "1484"

Test #12:

score: 0
Accepted
time: 2ms
memory: 42512kb

input:

500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1502

result:

ok "1502"

Subtask #3:

score: 20
Accepted

Test #13:

score: 20
Accepted
time: 2ms
memory: 42504kb

input:

500 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 ...

output:

1088

result:

ok "1088"

Test #14:

score: 0
Accepted
time: 3ms
memory: 42508kb

input:

500 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 ...

output:

1100

result:

ok "1100"

Test #15:

score: 0
Accepted
time: 2ms
memory: 42536kb

input:

500 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 ...

output:

1089

result:

ok "1089"

Test #16:

score: 0
Accepted
time: 1ms
memory: 42652kb

input:

500 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 ...

output:

1099

result:

ok "1099"

Test #17:

score: 0
Accepted
time: 2ms
memory: 42500kb

input:

500 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 ...

output:

1085

result:

ok "1085"

Test #18:

score: 0
Accepted
time: 2ms
memory: 42500kb

input:

500 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 ...

output:

1087

result:

ok "1087"

Subtask #4:

score: 7
Accepted

Test #19:

score: 7
Accepted
time: 165ms
memory: 394524kb

input:

5000 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0...

output:

10836

result:

ok "10836"

Test #20:

score: 0
Accepted
time: 163ms
memory: 394536kb

input:

5000 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0...

output:

10782

result:

ok "10782"

Test #21:

score: 0
Accepted
time: 161ms
memory: 394408kb

input:

5000 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0...

output:

10795

result:

ok "10795"

Test #22:

score: 0
Accepted
time: 163ms
memory: 394536kb

input:

5000 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0...

output:

10830

result:

ok "10830"

Test #23:

score: 0
Accepted
time: 165ms
memory: 394688kb

input:

5000 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1...

output:

10809

result:

ok "10809"

Test #24:

score: 0
Accepted
time: 165ms
memory: 394640kb

input:

5000 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0...

output:

10743

result:

ok "10743"

Test #25:

score: 0
Accepted
time: 163ms
memory: 394408kb

input:

5000 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1...

output:

10801

result:

ok "10801"

Test #26:

score: 0
Accepted
time: 166ms
memory: 394564kb

input:

5000 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0...

output:

10786

result:

ok "10786"

Test #27:

score: 0
Accepted
time: 163ms
memory: 394652kb

input:

5000 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1...

output:

10778

result:

ok "10778"

Test #28:

score: 0
Accepted
time: 164ms
memory: 394564kb

input:

5000 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0...

output:

10810

result:

ok "10810"

Test #29:

score: 0
Accepted
time: 162ms
memory: 394488kb

input:

5000 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1...

output:

10750

result:

ok "10750"

Test #30:

score: 0
Accepted
time: 165ms
memory: 394572kb

input:

5000 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0...

output:

10804

result:

ok "10804"