2023CCPC秦皇岛 F. Mystery of Prime(线性DP)

Problem - F - Codeforces

可以发现如果前面的数+当前数不是质数，如果要改当前的数，当前的数必须改成奇偶性跟前面数不同的数;然后可以发现1很特殊,因为1+1=2,2是质数，不满足以上规则，需要将1分开讨论

知道这两点就已经可以做题了，显然是一个线性DP，开四个状态分别表示当前数不改，改成1，改成偶数，改成奇数且前面都合法的最小方案

一些细节写在注释上

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
#define endl '\n'
#define pii pair<int, int>
#define lowbit(x) (x & (-x))
int vis[N];
void init()
{for (int i = 2; i < N; i++){if (vis[i])continue;for (int j = i + i; j < N; j += i)vis[j] = 1;}
}
int n;
int a[N];
int dp[N][5];
void solve()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];memset(dp, 0x3f, sizeof dp);dp[1][0] = 0;dp[1][1] = dp[1][2] = dp[1][3] = 1;// dp[i][0]表示第i位不变，且前面都合法的最小方案// dp[i][1]表示第i位改为1，且前面都合法的最小方案// dp[i][2]表示第i位改为偶数，且前面都合法的最小方案// dp[i][3]表示第i位改为奇数，且前面都合法的最小方案for (int i = 2; i <= n; i++){// 讨论0如何从前面的0,1,2,3转移过来if (!vis[a[i - 1] + a[i]]) // 前面数+当前数是质数，现在可以不变dp[i][0] = dp[i - 1][0];if (vis[a[i] + 1] == 0) // 前面是1，前面数+当前数是质数，现在可以不变dp[i][0] = min(dp[i][0], dp[i - 1][1]);if (a[i] % 2) // 当前是奇数，前面被改为偶数的时候，现在可以不变dp[i][0] = min(dp[i][0], dp[i - 1][2]);else // 当前是偶数，前面被改为奇数的时候，现在可以不变dp[i][0] = min(dp[i][0], dp[i - 1][3]);// 讨论1如何从前面的0,1,2转移过来(1无法从前面的3转移，因为两个奇数一定组成偶数)if (vis[a[i - 1] + 1] == 0) // 前面不变，现在填1能变为质数dp[i][1] = dp[i - 1][0] + 1;dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1); // 前面是1，现在填1dp[i][1] = min(dp[i][1], dp[i - 1][2] + 1); // 前面是偶数，现在填1(1也是奇数)// 讨论2如何从前面的0,1,3转移过来(2无法从前面的2转移，偶数+偶数一定是偶数)if (a[i - 1] % 2) // 前面数原本就是奇数，当前数改为偶数dp[i][2] = dp[i - 1][0] + 1;dp[i][2] = min(dp[i][2], dp[i - 1][1] + 1); // 前面数是1，当前数改为偶数dp[i][2] = min(dp[i][2], dp[i - 1][3] + 1); // 前面数是奇数，当前数改为偶数// 讨论3如何从前面的0,2转移过来(3无法从1,3转移，奇数+奇数一定是偶数)if (a[i - 1] % 2 == 0)dp[i][3] = dp[i - 1][0] + 1;dp[i][3] = min(dp[i][3], dp[i - 1][2] + 1);}// for (int i = 1; i <= n; i++)// {//     cout << a[i] << "   ";//     for (int j = 0; j <= 3; j++)//     {//         cout << dp[i][j] << ' ';//     }//     cout << endl;// }cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) << endl;
}signed main()
{init();ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--)solve();
}