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;}