分析
这题不用优化?
状态设计:设f [ i ] [ j ] :长度为 i ,以 a [ j ] 为结尾的严格上升子序列
如果要优化的用树状数组+离散化,可以减少一重循环代码(普通)
int T;scanf("%d",&T); for (int u=1;u<=T;u++) { memset(f,0,sizeof(f)); scanf("%lld%lld",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); a[0]=-1e9;f[0][0]=1; for (int i=1;i<=m;i++)//长度 for (int k=i;k<=n;k++)//当前 for (int j=0;j<k;j++)//上一个 { if(a[k]>a[j]) f[i][k]=(f[i][k]+f[i-1][j])%mod; } ll ans=0; for (int i=1;i<=n;i++) ans=(ans+f[m][i])%mod; printf("Case #%d: %lld\n",u,ans); }
代码(优化)
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") /* (写点什么吧...) */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=1e3+10; const ll mod=1e9+7; ll n,m,cnt; ll a[N],f[N][N],b[N],s[N]; inline int lowbit(int x) { return x&(-x); } inline void add(ll x,ll z) { while(x<=n+1) { s[x]+=z; s[x]%=mod; x+=lowbit(x); } } inline ll ask(ll x) { ll ret=0; while(x) { ret+=s[x]; ret%=mod; x-=lowbit(x); } return ret; } int main() { int T;scanf("%d",&T); for (int u=1;u<=T;u++) { scanf("%lld%lld",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); int cnt=unique(b+1,b+n+1)-b-1; for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b; memset(f,0,sizeof(f)); f[0][0]=1; for (int i=1;i<=m;i++) { memset(s,0,sizeof(s)); add(1,f[i-1][0]); for (int k=1;k<=n;k++) { f[i][k]=ask(a[k]); add(a[k]+1,f[i-1][k]); } } ll ans=0; for (int i=1;i<=n;i++) ans=(ans+f[m][i])%mod; printf("Case #%d: %lld\n",u,ans); } return 0; }