HDU P5542 The Battle of Chibi

目录：

• 题目：
• 分析：
• 代码：

题目：

传送门

分析：

$f[i][j]$，表示到第$i$个数字，长度为$j$的单调递增子序列的个数。需要注意的是取第$j$个数字。

代码：

#include
#include
#include
#include  
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define h happy
#define XJQ 1000000007
using namespace std;
inline LL read() {LL d=0,f=1;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}return d*f;
}
int q=read(),n,m,f[1001][1001];
void add(int x,int y,int w)
{for(;x<=n;x+=x&-x){f[x][y]+=w;if(f[x][y]>=XJQ) f[x][y]%=XJQ;}
}
int ask(int x,int y)
{int ans=0;for(;x;x-=x&-x){ans+=f[x][y];if(ans>=XJQ) ans%=XJQ;}return ans;
}
int a[1001],b[1001];
int main()
{int k=0;while(q--){n=read();m=read();memset(f,0,sizeof(f));for(int i=1;i<=n;i++) a[i]=b[i]=read();sort(b+1,b+1+n);for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+n,a[i])-b;for(int i=1;i<=n;i++){add(a[i],1,1);for(int j=2;j<=min(i+1,m);j++){int long_king=ask(a[i]-1,j-1);add(a[i],j,long_king);}}printf("Case #%d: %d\n",++k,ask(n,m));}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！