首页 > 代码库 > zoj1283(LIS)
zoj1283(LIS)
题意:宝藏在一些点中,只能从(0,0)出发,每次只能向右(x+1,y)或是向上走(x,y+1)。问要走几趟才能取完宝藏。
解法:按x,y分别为第一二关键字排序,那么一趟下来,y坐标是个非递减序列。然后转化成问y方向能由最少为多少的非递减序列个数组成。这个等效于求严格递减序列的长度。即nlogn求最长严格递减序列长度即可。
代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=2010; const LL INF=1000000007; LL C[Max][Max]; LL st[Max][Max]; int n,a,b; void init() { st[0][0]=1; C[0][0]=1; for(int i=1;i<Max;i++) for(int j=0;j<=i;j++) { C[i][j]= j==0?1:(C[i-1][j-1]+C[i-1][j])%INF; st[i][j]= j==0?0:(st[i-1][j-1]+st[i-1][j]*(i-1)%INF)%INF; } } int main() { int t; cin>>t; init(); while(t--) { scanf("%d%d%d",&n,&a,&b); if(a+b>n+1) cout<<"0"<<endl; else cout<<C[a+b-2][a-1]*st[n-1][a+b-2]%INF<<endl; } return 0; }
zoj1283(LIS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。