首页 > 代码库 > HDU2227 Find the nondecreasing subsequences
HDU2227 Find the nondecreasing subsequences
题解:
dp+树状数组优化
dp[i]表示以i结尾时的非递减数组和.这样做的复杂度是o(n^2)，不行
观察这个dp
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++) if(a[j]<=a[i]) dp[i]=(dp[i]+dp[j])%mod;
}
dp[i]求的是前面全部小于等于a[i]的a[j]的dp[j]的和
那么，可以每次把dp[j]加入到树状数组中,
也就是每次 dp[i]=sum(a[i]);求的是每次小于等于a[i]的dp和,然后add(a[i],dp[i]+1)
最后求sum(maxn)即可
代码:
o(n^2) TLE
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=100010;const int mod=1000000007;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------int a[maxn];int dp[maxn];int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ dp[i]=1; for(int j=1;j<i;j++) if(a[j]<=a[i]) dp[i]=(dp[i]+dp[j])%mod; } int sum=0; for(int i=1;i<=n;i++) sum=(sum+dp[i])%mod; printf("%d\n",sum);}
o(nlog(n))
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=100010;const int mod=1000000007;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------pair<int,int> p[maxn];int b[maxn],c[maxn];int dp[maxn];int lowbit(int x) {return x&-x;}void add(int x,int v){ while(x<maxn){ c[x]+=v; c[x]%=mod; x+=lowbit(x); }}int sum(int x){ int cnt=0; while(x){ cnt+=c[x]; cnt%=mod; x-=lowbit(x); } return cnt;}int main(){ int n; while(~scanf("%d",&n)){ CLR(c); for(int i=1;i<=n;i++){ scanf("%d",&p[i].fs); p[i].se=i; b[i]=p[i].fs; } sort(p+1,p+n+1); for(int i=1;i<=n;i++) b[p[i].se]=i; for(int i=1;i<=n;i++){ dp[i]=sum(b[i]); add(b[i],dp[i]+1); } printf("%d\n",sum(maxn)); }}
HDU2227 Find the nondecreasing subsequences
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。