hdu.5542-The Battle of Chibi

The Battle of Chibi

• 分析

  这题不用优化?
  状态设计：设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;
}