UVA - 12983 The Battle of Chibi（树状数组+DP）
HDU - 5542 The Battle of Chibi（树状数组+DP）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int n,m,a[N],tr[N],f[N][N];
void add(int x,int v)
{
for(int i=x;i<=n;i+=(i&-i))tr[i]=(tr[i]+v)%MOD;
}int sum(int x)
{
int res=0;for(int i=x;i>0;i-=(i&-i))res=(res+tr[i])%MOD;return res;
}int main()
{
int T;scanf("%d",&T);for(int C=1;C<=T;C++){
vector<int> nums;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){
scanf("%d",&a[i]);nums.push_back(a[i]);}sort(nums.begin(),nums.end());nums.erase(unique(nums.begin(),nums.end()),nums.end());for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;for(int i=1;i<=n;i++) f[i][1]=1;for(int j=2;j<=m;j++){
for(int i=1;i<=n;i++) tr[i]=0;for(int i=1;i<=n;i++){
f[i][j]=sum(a[i]-1);add(a[i],f[i][j-1]);}}int res=0;for(int i=1;i<=n;i++) res=(res+f[i][m])%MOD;printf("Case #%d: %d\n",C,res);}return 0;
}