ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#534 | #113. 【0621 模拟赛】Zrinka | ryp | 100 | 1611ms | 199116kb | C++14 | 872b | 2025-06-20 09:53:21 | 2025-06-21 23:20:55 |
answer
#include<bits/stdc++.h>
using namespace std;
int dp[5005][5005][2];
int n,m,a[5005],b[5005];
const int inf=1e9;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//IO优化
cin>>n;for(int i=1;i<=n;++i) cin>>a[i];
cin>>m;for(int i=1;i<=m;++i) cin>>b[i];
for(int i=0;i<=n;++i){
for(int j=0;j<=m;++j){
if(i==0&&j==0) continue;//这种情况不存在
dp[i][j][0]=inf;
//为防止代码过长,加以适当简化
if(i){
dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+1+(bool)(a[i]==a[i-1]));
dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+1+(bool)(a[i]==b[j]));
}
dp[i][j][1]=inf;
if(j){
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+1+(bool)(b[j]==b[j-1]));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+1+(bool)(b[j]==a[i]));
}
}
}
cout<<min(dp[n][m][0],dp[n][m][1]);//输出最优方案
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 0ms
memory: 3284kb
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: 3284kb
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: 3292kb
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: 0ms
memory: 3316kb
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: 0ms
memory: 3244kb
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: 3276kb
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: 3ms
memory: 22112kb
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: 2ms
memory: 22100kb
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: 4ms
memory: 22024kb
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: 3ms
memory: 22008kb
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: 1ms
memory: 22100kb
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: 1ms
memory: 22272kb
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: 1ms
memory: 22216kb
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: 1ms
memory: 22144kb
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: 4ms
memory: 22308kb
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: 2ms
memory: 22180kb
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: 22216kb
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: 1ms
memory: 22272kb
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: 131ms
memory: 198948kb
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: 134ms
memory: 198736kb
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: 133ms
memory: 199116kb
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: 132ms
memory: 198864kb
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: 132ms
memory: 198940kb
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: 128ms
memory: 198944kb
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: 132ms
memory: 198936kb
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: 132ms
memory: 198896kb
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: 133ms
memory: 199000kb
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: 132ms
memory: 198948kb
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: 133ms
memory: 198972kb
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: 132ms
memory: 199116kb
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"