HDU - 5542 C - The Battle of Chibi （dp+树状数组)

题目大意：
给你t个样例
给你两个数n,m
再给你n个数，让你在n个数中找长度为m的子序列（不必连续）有多少种

思路：
dp+树状数组优化
我们用dp[i][j]表示长度为i以a[j]为结尾的子序列有多少个
那么正常来说就是
dp[i][j]+=dp[i-1][k] (a[k] 但是因为i和j要遍历m与n已经两重循环了
再加上一个k三重循环就会T了
这个时候我们可以用树状数组来优化
把dp[i-1][k]全部存起来
因为我们其实不需要k的确切值
我们只要a[k]小于a[j]的长度为i-1的方案数就好了
这样就能优化到n²logn
同时注意一下离散化数据就好了

AC代码：

#include 
#define lower_bit(x) (x)&(-x)
using namespace std;
typedef long long ll;
const int N=1e3+10;
ll a[1010];
const int mod=1000000007;
ll c[1010];
ll dp[1010][1010];
vector<ll>v;
ll n,m;
void add(ll x,ll k)
{while(x<=n+2)//因为下标是从2开始的{c[x]+=k;c[x]%=mod;x+=lower_bit(x);}return;
}
ll getsum(ll x)
{ll cnt=0;while(x){cnt+=c[x];cnt%=mod;x-=lower_bit(x);}return cnt;
}
int main()
{ios::sync_with_stdio(false),cin.tie(0);int t;cin>>t;int kase=0;while(t--){memset(dp,0,sizeof(dp));v.clear();cin>>n>>m;ll ans=0;for(int i=1; i<=n; i++){cin>>a[i];v.push_back(a[i]);}sort(v.begin(),v.end());//离散化v.erase(unique(v.begin(),v.end()),v.end());for(int i=1; i<=n; i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+2;dp[0][0]=1;add(1,dp[0][0]);//要确保1是最小的所以上面下标从2开始for(int i=1; i<=m; i++){for(int j=1; j<=n; j++){dp[i][j]=getsum(a[j]-1);//看比a[j]小的长度为i-1方案数有多少个dp[i][j]%=mod;add(a[j],dp[i-1][j]);}memset(c,0,sizeof(c));}for(int j=1; j<=n; j++){ans+=dp[m][j]%mod;ans%=mod;}cout<<"Case #"<<++kase<<": ";cout<<ans<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！