首页 > 代码库 > 【noi 2.6_9289】&【bzoj2023 / 1630】Ant Counting 数蚂蚁{Usaco2005 Nov}

【noi 2.6_9289】&【bzoj2023 / 1630】Ant Counting 数蚂蚁{Usaco2005 Nov}

题意:有M个家族的蚂蚁,各Ni只(互相相同)。问选出 l~r 只的不同组合数。

解法:很基础的一种DP,不要被“排列组合”所迷惑了啊~我之前接触过这个类型,可惜又忘了,一定要记住!
这是一种类型的DP——M种N个进行DP,定义f[i][j]表示前 i 种中(这题是“家族”)选了 j 个(“只”蚂蚁)的方案数。再进行分层DP

所以f[i][j]=sum{f[i-1][j-k]} (0<=k<=Ni),再利用前缀和优化时间+滚动数组优化空间就可以了。

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define M 1010 8 #define N 100010 9 #define mod 100000010 11 int a[N],h[M],f[2][N];//h[i]就是题目中的Ni12 int mmin(int x,int y) {return x<y?x:y;}13 14 int main()15 {16     int m,n,l,r;17     scanf("%d%d%d%d",&m,&n,&l,&r);18     for (int i=1;i<=n;i++) scanf("%d",&a[i]);19     sort(a+1,a+1+n);20     int t=1; h[1]=1,h[m+1]=n+1;21     for (int i=2;i<=n;i++)22       if (a[i]!=a[i-1]) h[++t]=i;23   24     f[0][0]=1;25     for (int j=1;j<h[2];j++) f[0][j]=0;26     int u=1;27     for (int i=1;i<=m;i++)28     {29       f[u][0]=1;30       for (int j=1;j<h[i+1];j++)31       {32         int k=mmin(h[i+1]-h[i],j);33         f[u][j]=((f[u][j-1]+f[1-u][j])%mod-f[1-u][j-k-1]%mod+mod)%mod;34         //for (int k=0;k<=h[i+1]-h[i]&&k<=j;k++)35         //  f[i][j]+=f[i-1][j-k];36       }37       u=1-u;38     }39     int ans=0;40     for (int j=l;j<=r;j++) ans=(ans+f[1-u][j])%mod;41     printf("%d\n",ans);42     return 0;43 }

 

【noi 2.6_9289】&【bzoj2023 / 1630】Ant Counting 数蚂蚁{Usaco2005 Nov}