HDU 2227 Find the nondecreasing subsequences
1306 ワード
1つのシーケンスを与え、そのすべての上昇サブシーケンスを求める.
问题解:最初は动态计画だと思っていましたが、离散后の木の配列がよくできていることに気づきました.まず、cが保存しているのはi位上升子シリーズがいくつかあるので、木の配列のsumは直接今の答えですが、更新时に1を加えることを忘れないでください.今の要素自体もサブシーケンスです.例えば、数列离散后は1 3 2 4 5です.では,1位で得られた前の答えは0,更新時に1位に1,2位で1,更新時に3位に(1+1),3位でも同様に1回類推して木配列の逆配列を求める方法と同様であるが,更新したのは1ではなく,前のすべての答え数に1を加える.
问题解:最初は动态计画だと思っていましたが、离散后の木の配列がよくできていることに気づきました.まず、cが保存しているのはi位上升子シリーズがいくつかあるので、木の配列のsumは直接今の答えですが、更新时に1を加えることを忘れないでください.今の要素自体もサブシーケンスです.例えば、数列离散后は1 3 2 4 5です.では,1位で得られた前の答えは0,更新時に1位に1,2位で1,更新時に3位に(1+1),3位でも同様に1回類推して木配列の逆配列を求める方法と同様であるが,更新したのは1ではなく,前のすべての答え数に1を加える.
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100005;
const int mod=1000000007;
struct node{int id,v;}a[N];
int b[N],c[N],n;
bool cmp(node a,node b){return a.v<b.v;}
int sum(int x){int s=0;while(x>0)s+=c[x],s%=mod,x-=x&-x;return s;}
void updata(int x,int num){while(x<=n)c[x]+=num,c[x]%=mod,x+=x&-x;}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<=n;i++)b[i]=c[i]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i].v);
a[i].id = i;
}
sort(a+1,a+n+1,cmp);
b[a[1].id]=1;
for(int i=2;i<=n;i++){
if(a[i].v!=a[i-1].v)b[a[i].id]=i;
else b[a[i].id]=b[a[i-1].id];
}
for(int i=1;i<=n;i++)updata(b[i],sum(b[i])+1);
printf("%d
",sum(n));
}
return 0;
}