php是做网站还是网页,网站建设大型企业,株洲有几个区,品牌注册和商标注册有什么区别题目要求改变数组中的数字使相邻数字之和是质数#xff0c;同时改变数字的次数最少
因为改变的数字可以无穷大
我假设当一个数改变为一个某一个偶数时#xff0c;他周围的任意的奇数肯定能和他相加变成质数
当一个数变为某一个大于1的奇数时#xff0c;他周围任意偶数肯定…题目要求改变数组中的数字使相邻数字之和是质数同时改变数字的次数最少
因为改变的数字可以无穷大
我假设当一个数改变为一个某一个偶数时他周围的任意的奇数肯定能和他相加变成质数
当一个数变为某一个大于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] });
}
