传送
特写此篇，纪念不用dp做dp题
洛谷说这是个dp,但我不信（其实就是不会dp)，因此我们考虑用另一种思路。修改后的队列每一个 数a[i]一定满足a[i]<=a[i+1],那修改后的顺序就是一个不下降序列。为了求出最少要改的数，只要求出原来的序列中最长不下降子序列的长度l,再用n减去即可。求l的方式和导弹拦截的(1)差不多，只需要改大于小于就行。(详情请见邱大佬的导弹拦截题解)
代码奉上
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int l=1,k=1,n,a[30001],f[30001]; void bxjzxlxz(int u) { for(int i=1;i<=l;i++) { if(f[i]>a[u]) {f[i]=a[u];break; } } } void bxjzxl() { for(int i=2;i<=n;i++) { if(a[i]>=f[l]) {f[++l]=a[i]; } else bxjzxlxz(i);//最长不下降子序列寻找 } } int main() {cin>>n; for(int i=1;i<=n;i++) {cin>>a[i]; } f[1]=a[1]; bxjzxl();//最长不下降子序列int ans=n-l; cout<<ans; }ps:求教dp做法
orz各位大神
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
qwq
转载于:https://www.cnblogs.com/lcez56jsy/p/10598147.html
相关资源：数据结构—成绩单生成器