ccpc2023秦皇岛F. Mystery of Prime(dp)

秦皇岛F. Mystery of Prime(dp)"/>

ccpc2023秦皇岛F. Mystery of Prime(dp)

题目要求改变数组中的数字使相邻数字之和是质数，同时改变数字的次数最少

因为改变的数字可以无穷大

我假设当一个数改变为一个某一个偶数时，他周围的任意的奇数肯定能和他相加变成质数

当一个数变为某一个大于1的奇数时，他周围任意偶数肯定能和他相加变成质数

当一个数变为1时，他周围的1一定是符合条件的，同时如果有修改成偶数的也一定符合条件

我们就可以开4维的dp

0修改成大于1的奇数，1修改成偶数，2修改成1, 3不修改

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 50;
int dp[N][4];//0修奇数, 1修偶数, 2修1,3不修
int a[N]; int v[N], prime[N];
int m;
void is_prime()
{for (int i = 2; i < N; i++){if (v[i] == 0) { v[i] = i; prime[++m] = i; }for (int j = 1; j <= m; j++) { if (prime[j] > v[i] || prime[j] > N / i) break; v[i * prime[j]] = prime[j]; }}
}
bool check(int x) { if (v[x] == x) return true; return false; }
signed main() {ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); is_prime();int n; cin >> n; for (int i = 1; i <= n; i++) {cin >> a[i];}dp[1][0] = 1, dp[1][1] = 1; dp[1][2] = 1, dp[1][3] = 0; if (a[1] == 1) { dp[1][2] = 0; }for (int i = 2; i <= n; i++) {//0修奇数, 1修偶数, 2修1,3不修if (a[i] == 1) {//1 -> 偶数和1dp[i][3] = min(dp[i - 1][2], dp[i - 1][1]);}else if (a[i] & 1) {//奇数 -> 偶数dp[i][3] = dp[i - 1][1];}else {//偶数 -> 奇数和1dp[i][3] = dp[i - 1][0];if (check(a[i] + 1)) {dp[i][3] = min(dp[i][3], dp[i - 1][2]);}}if (check(a[i] + a[i - 1])) {// ->不修改dp[i][3] = min(dp[i][3], dp[i - 1][3]);}if (a[i] == 1) {dp[i][2] = dp[i][3];}else {//0修奇数, 1修偶数, 2修1,3不修dp[i][2] = min(dp[i - 1][2] + 1, dp[i - 1][1] + 1);//修改为1->1和偶数if (check(1 + a[i - 1])) {//->不修改dp[i][2] = min(dp[i][2], dp[i - 1][3] + 1);}}dp[i][0] = dp[i - 1][1] + 1;//奇数 -> 偶数if (a[i - 1] % 2 == 0) {dp[i][0] = min(dp[i][0], dp[i - 1][3] + 1);}dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][2] + 1);//偶数 -> 1和奇数if (a[i - 1] % 2 == 1) {dp[i][1] = min(dp[i][1], dp[i - 1][3] + 1);}}cout << min({ dp[n][0],dp[n][1],dp[n][2],dp[n][3] });
}