(Nowcoder 2019国庆day5) E.Longest Increasing Subsequence（动态规划+思维）

本文主要是介绍(Nowcoder 2019国庆day5) E.Longest Increasing Subsequence（动态规划+思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题意：f[i]是以i结尾的最长不下降子序列长度，问删掉第i个数后f[1]^2 xor f[3]^2 xor .. xor f[n]^2（不算第i个）

解: 如果对最长不下降子序列理解的彻底的会觉得很简单吧，我们可以考虑到当不考虑一个数是，那有些f[i]可能会不受影响或者-1，但是我们如何快速得出呢。当然是先全部求一遍f[]了，然后我们需要一个mi[]数组，mi[i]定义为长度为i的不下降子序列长度的最小结尾，对于每个j，我们考虑是不是mi[f[j]-1]<a[j]，如果是那么当前j为的LIS还是f[j]（因为可以放a[j]嘛），反之就是不能了，那就是f[j]-1了。

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=5e3+5;
//il int Add(int &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(int &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,a[N],lis[N],mi[N];//mi[i]：lis长度为i的最小结尾 
int main(){std::ios::sync_with_stdio(0);cin.tie(0);vector<int> v;while(cin>>n){for(int i=1;i<=n;++i) cin>>a[i];v.clear();	for(int i=1;i<=n;++i){int p=lower_bound(v.begin(),v.end(),a[i])-v.begin();if(p==SZ(v)) v.pb(a[i]);else v[p]=a[i];lis[i]=p+1;}int ans=0;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j) mi[j]=inf;mi[0]=0,ans=0;for(int j=1;j<=n;++j){if(j==i) continue;if(mi[lis[j]-1]<a[j]){ans^=lis[j]*lis[j];mi[lis[j]]=min(mi[lis[j]],a[j]);}else{ans^=(lis[j]-1)*(lis[j]-1);mi[lis[j]-1]=min(mi[lis[j]-1],a[j]);} }cout<<ans<<" ";}cout<<endl;}return 0;
}

 

这篇关于(Nowcoder 2019国庆day5) E.Longest Increasing Subsequence（动态规划+思维）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---