首页 > 代码库 > 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)