[HDU 5542] The Battle of Chibi

[题目链接]

         http://acm.hdu.edu.cn/showproblem.php?pid=5542

[算法]

       树状数组优化DP

[代码]

        

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010
const int P = 1e9 + 7;

int i,j,T,TC,n,m,len,ans;
int a[MAXN],tmp[MAXN],rk[MAXN];
int f[MAXN][MAXN];

class BinaryIndexedTree
{
    private :
        int c[MAXN];
    public :
        inline int lowbit(int x)
        {
            return x & (-x);
        }
        inline void clear()
        {
            memset(c,0,sizeof(c));
        }
        inline void modify(int pos,int val)
        {
            int i;
            for (i = pos; i <= len; i += lowbit(i)) c[i] =(c[i] + val) % P;
        }
        inline int query(int pos)
        {
            int i;
            int ret = 0;
            for (i = pos; i; i -= lowbit(i)) ret = (ret + c[i]) % P;
            return ret;
        }
} BIT;

int main()
{
    
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        for (i = 1; i <= n; i++) 
        {
            scanf("%d",&a[i]);
            tmp[i] = a[i];    
        }    
        sort(tmp+1,tmp+n+1);
        len = unique(tmp+1,tmp+n+1) - tmp - 1;
        for (i = 1; i <= n; i++) rk[i] = lower_bound(tmp+1,tmp+len+1,a[i]) - tmp;
        for (i = 1; i <= n; i++) f[1][i] = 1;
        for (i = 2; i <= m; i++)
        {
            BIT.clear();
            for (j = 1; j <= n; j++)
            {
                f[i][j] = BIT.query(rk[j] - 1);
                BIT.modify(rk[j],f[i-1][j]);
            }
        }
        ans = 0;
        for (i = 1; i <= n; i++) ans = (ans + f[m][i]) % P;
        printf("Case #%d: %d\n",++TC,ans);
    }
    
    return 0;
}