嚴格上升子序列數
解題思路
這題跟P1908 逆序對（樹狀陣列）（離散化優化）有異曲同工之妙
可推出式子
（設f(i,j)表示以第i個數結尾、長度為j的嚴格上升子序列數）
當然
當j=1時結果為1
再用離散化優化
AC代碼
#include<algorithm>
#include<cstring>
#include<cstdio>
long long n,m,a[1005],b[1005],c[1005][1005],f[1005][1005];
using namespace std;
long long lowbit(long long x)
{
return x&(-x);
}
void update(long long x,long long i,long long y)//存盤
{
for(;i<=n;i+=lowbit(i))c[x][i]+=y;
}
long long query(long long x,long long i)//查詢
{
long long sum=0;
for(;i;i-=lowbit(i))sum+=c[x][i];
return sum;
}
int main()
{
long long T,t=0;
scanf("%lld",&T);
while(T--)
{
long long ans=0;
memset(f,0,sizeof(f));
memset(c,0,sizeof(c));
t++;
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)scanf("%lld",&a[i]);
for(long long i=1;i<=n;i++)b[i]=a[i];//離散化
sort(b+1,b+n+1);
long long tot=unique(b+1,b+1+n)-1-b;
for(long long i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
for(long long i=1;i<=n;i++)//dp
for(long long j=1;j<=m;j++)
{
if(j==1)f[i][j]=1;
else f[i][j]=query(j-1,a[i]-1);
update(j,a[i],f[i][j]);
}
for(long long i=m;i<=n;i++)ans+=f[i][m];
printf("Case #%lld: %lld\n",t,ans);
}
}
謝謝
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287247.html
標籤：其他