郑州企业的网站建设,wordpress会员破解,如何建立平台网站,自己房子怎么挂网站做民宿题目传送门 题目不是很难#xff0c;看了一会就想到了#xff0c;但因为一些细节WA了好几遍qwq 但代码却一点一点压短了#xff08;看了别人的精简写法#xff09; 题目分析 把一个序列改成不上升或不下降子序列#xff0c;求最少修改次数。 一般情况有求 LIS 和 LDS 的 O… 题目传送门 题目不是很难看了一会就想到了但因为一些细节WA了好几遍qwq 但代码却一点一点压短了看了别人的精简写法 题目分析 把一个序列改成不上升或不下降子序列求最少修改次数。 一般情况有求 LIS 和 LDS 的 O(nlogn) 做法但由于本题只出现 1 2 3 三个数字可进一步优化为O(n) 。 先考虑由 1 到 3 递增递减反之 用 f[i][j] 表示前i个数第 i 个数字是 j 的 最优解 有两种情况 1、第 i 个与第 i-1 个数字一样 此时 f[i][j] f[i-1][j]; if (a[i] ! j) f[i][j]; 简写 f[i][j] f[i-1][j] (a[i] ! j); 2、第 i 个比 第 i-1 个大 又分 3 种从 1 到 3 从 2 到 3 从1 到 2 在按降序做一遍取最小值 注意 1、本题不一定要有 1、2、3 三种数字可以只有几种这就是我错的原因...... 2、1 后不一定是 2可能直接到 3 代码 #include bits/stdc.h
using namespace std;
int n, a[30008], f1[30008][3], f2[30008][3];
int main() {scanf (%d, n);for (int i 1; i n; i) scanf (%d, a i);for (int i 1; i n; i){f1[i][0] f1[i-1][0] (a[i] ! 1); f1[i][1] min (f1[i-1][1], f1[i-1][0]) (a[i] ! 2);f1[i][2] min (f1[i][1] - (a[i] ! 2), f1[i-1][2]) (a[i] ! 3); //代码压缩后没有那么一目了然但还是比较好理解 }for (int i 1; i n; i){f2[i][0] f2[i-1][0] (a[i] ! 3); f2[i][1] min (f2[i-1][1], f2[i-1][0]) (a[i] ! 2);f2[i][2] min (f2[i][1] - (a[i] ! 2), f2[i-1][2]) (a[i] ! 1);}printf (%d\n, min(min(f1[n][0], f2[n][0]), min(min(f1[n][1], f2[n][1]), min(f1[n][2], f2[n][2]))));//取 6 种情况的最小值 return 0;
}转载于:https://www.cnblogs.com/whx666/p/11129807.html
