网站开发从事,wordpress 密匙 和授权,做商城网站需要准备那些,网站开发常用工具文章目录题目描述解析1.n^2^朴素算法2.队列nlogn算法代码3.二维DP#xff08;n^2^)代码thanks for reading!题目描述
五一到了#xff0c;PKU-ACM队组织大家去登山观光#xff0c;队员们发现山上一个有N个景点#xff0c;并且决定按照顺序来浏览这些景点#xff0c;即每次…
文章目录题目描述解析1.n^2^朴素算法2.队列nlogn算法代码3.二维DPn^2^)代码thanks for reading!题目描述
五一到了PKU-ACM队组织大家去登山观光队员们发现山上一个有N个景点并且决定按照顺序来浏览这些景点即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯就是不连续浏览海拔相同的两个景点并且一旦开始下山就不再向上走了。队员们希望在满足上面条件的同时尽可能多的浏览景点你能帮他们找出最多可能浏览的景点数么输入 Line 1 N (2 N 1000) 景点数 Line 2 N个整数每个景点的海拔 输出 最多能浏览的景点数 样例输入 8 186 186 150 200 160 130 197 220 样例输出 4
解析
三种方法
1.n2朴素算法
就是前后各跑一遍最长上升序列然后扫一遍进行最优决策
for(int i1;in;i) ansmax(ans,x[i]y[i]-1);代码就不贴了
2.队列nlogn算法
就是第一个使用队列的优化但是没有一次AC 因为这里虽然是最长上升但是不能取等所以应该使用lowwerbound 机制也不难理解因为不带等所以队列中显然不能有一样的元素 找个简单的例子就能很容易的看出来
输入
1 5 8 5 7
过程
i1: 1
i2: 1 5
i3: 1 5 8
i4: 1 5(相当于把自己替换 8
i5: 1 5 7
ans3
如果用upperbound显然就会错误 这个收获挺大的 学废了
代码
#includebits/stdc.h
using namespace std;
const int N150;
int n,m;
int a[N],x[N],y[N];
int q[N],ed;
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i){if(a[i]q[ed]) q[ed]a[i];else{int pllower_bound(q1,q1ed,a[i])-q;q[pl]a[i];}x[i]ed;}memset(q,0,sizeof(q));ed0;for(int in;i1;i--){if(a[i]q[ed]) q[ed]a[i];else{int pllower_bound(q1,q1ed,a[i])-q;q[pl]a[i];}y[i]ed;}int ans0;for(int i1;in;i) ansmax(ans,x[i]y[i]-1);printf(%d,n-ans);return 0;
}
/*
8
186 186 150 200 160 130 197 220
*/3.二维DPn2)
就是再加一维状态记录是否开始增减 这样代码会很短 但复杂度还是平方 但是 这个和朴素最长单调序列一样最优答案未必在最后
代码
#includebits/stdc.h
using namespace std;
const int N150;
int n,m;
int a[N],dp[N][3];
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i){dp[i][1]dp[i][2]1;for(int j1;ji;j){if(a[j]a[i]) dp[i][1]max(dp[i][1],dp[j][1]1);else if(a[j]a[i]){dp[i][2]max(dp[i][2],dp[j][2]1);dp[i][2]max(dp[i][2],dp[j][1]1);}}}printf(%d,n-max(dp[n][1],dp[n][2]));return 0;
}
/*
5
3
*/thanks for reading!
