<span>HDU5542 The Battle of Chibi（dp）</span>
题意：
给你一个长度为n（1e3）的数列，让你找出长度为m的上升子序列的个数
思路：
f[i][j]表示以第i个数为结尾，长度为j的上升子序列的个数，枚举i和j是n^2的，统计的时候用树状数组维护一下
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <unordered_map> #include <string> #include <time.h> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define pii pair<int,int> #define mkp make_pair #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=1e3+10; int t,n,m; int a[N],b[N],d[N][N]; int add(int &x,int y) { x+=y; if(x>=mod) x-=mod; } int lowbit(int x) { return x&(-x); } void update(int p,int x,int val) { while(x<=n) { add(d[p][x],val); x+=lowbit(x); } } int sum(int p,int x) { int ret=0; while(x>0) { add(ret,d[p][x]); x-=lowbit(x); } return ret; } int main() { scanf("%d",&t); for(int cas=1;cas<=t;cas++) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b; memset(d,0,sizeof(d)); int ans=0; for(int i=1;i<=n;i++) { int top=min(i,m),f=1; update(1,a[i],1); for(int j=2;j<=top;j++) { f=sum(j-1,a[i]-1); update(j,a[i],f); } if(i>=m) add(ans,f); } printf("Case #%d: %d\n",cas,ans); } return 0; }
中移(苏州)软件技术有限公司工作强度 29人发布
