QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#712572 | #7624. Mystery of Prime | _lntano | WA | 1ms | 5700kb | C++20 | 2.0kb | 2024-11-05 16:12:31 | 2024-11-05 16:12:32 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
const int N=2e5+10,mod=1e9+7,M=1e6+10;
int dp[N][20];
int a[N];
int check(int x){
if(x==2)return 1;
for(int i=2;i*i<=x;i++){
if(x%i==0){
return 0;
}
}
return 1;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=0;i<=n;i++){
for(int j=0;j<=18;j++){
dp[i][j]=inf;
}
}
dp[1][0]=0;
dp[1][1]=1;
dp[1][2]=1;
dp[1][3]=1;
for(int i=2;i<=n;i++){
if(check(a[i]+a[i-1])){
dp[i][0]=min(dp[i-1][0],dp[i][0]);
}
if(check(a[i]+1)){
dp[i][0]=min(dp[i][0],dp[i-1][1]+1);
}
if(a[i]%2==0){
dp[i][0]=min({dp[i-1][3],dp[i][0]});
}
else {
dp[i][0]=min({dp[i-1][2],dp[i][0]});
}
if(a[i-1]%2==1){
dp[i][2]=min(dp[i-1][0]+1,dp[i][2]);
}
else {
if(check(a[i-1]+1)){
dp[i][1]=min(dp[i-1][0]+1,dp[i][1]);
}
dp[i][3]=min(dp[i-1][0]+1,dp[i][3]);
}
if(a[i]==1){
dp[i][0]=min(dp[i][0],dp[i-1][1]);
dp[i][1]=min(dp[i][1],dp[i][0]);
dp[i][0]=min(dp[i][1],dp[i][0]);
}
dp[i][2]=min({dp[i][2],dp[i-1][1]+1,dp[i-1][3]+1});
dp[i][1]=min({dp[i-1][2]+1,dp[i][1],dp[i-1][1]+1});
dp[i][3]=min(dp[i-1][2]+1,dp[i][3]);
}
int ans=inf;
ans=min({ans,dp[n][0],dp[n][1],dp[n][2],dp[n][3]});
cout<<ans;
}
signed main(){
GG;
int _t=1;
//cin>>_t;
while(_t--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5700kb
input:
6 1 5 1 4 4 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
9 30 6 7 12 15 8 20 17 14
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3844kb
input:
1568 119 519 706 1003 1317 322 25 1466 816 525 1 1122 38 1511 774 515 274 780 647 230 1602 1051 810 1 1 1232 1 1202 1583 412 1111 168 309 1181 184 1260 491 764 809 1213 804 1470 1 1087 1235 1004 673 1338 1333 1392 1036 1539 268 1 712 727 297 404 1317 36 463 1067 1133 693 931 46 1 100 1608 965 1 1406...
output:
745
result:
wrong answer 1st numbers differ - expected: '733', found: '745'