POJ - 3046 多重集组合数问题的线性DP（四种方法）
t 种蚂蚁，共a只，同种蚂蚁不区分，构成各种大小的不同多重集，问大小在闭区间[s,b]的多重集共有多少个
多重集的意思是元素可重复，构成元素或重数不同就是不同的多重集，比如{1,1,2,3}是一个多重集，这里的元素是蚂蚁的种类编号
这个题吧，其实有很多槽点
博主做这道题自认为做的很完美，但是WA了一个小时，完全找不到错误
后来一看，要求模1000000，没看到。。。
然后改了后又WA，立马意识到中间其实会爆int，过程中也要取模，不能最后求结果的时候只取一次模
然后第二个槽点是什么呢
这个题给的数据说 t 是 1e3 ，b<=a 是 1e5
我们平常写的朴素的算法的话，复杂度是 O(t*b^2) 是 1e13...
看这个说明肯定超时而且超的不止一点点...
于是博主就花时间想如何优化，然后绞尽脑汁只能优化成 O(t*b) 是 1e8...
然鹅前者就能过，这数据在搞神魔......
不嗦废话了...开始讲解...
法一：朴素O(t*b^2)
dp[i][j]表示前i种蚂蚁，取j个时的不同构成数
那么如何转移呢，特别简单
举个例子，之前是 {1} {2} {1,2} 这三个集合 dp[2][1]=2 , dp[2][2]=1
进来2个3，那么比如求dp[3][3]，就是一个的添上2个3，两个的添上一个3
dp[3][3]=dp[2][1]+dp[2][2]
你理解一下，就是说，转移方程是
利用背包的思想如果 j 从大到小更新，第一维就可以去掉
然后下面是代码
#include <cstdio>
#include <algorithm>
#define M 1000000
using namespace std;
int t,a,s,b,dp[100005]={1},x[1005],id,ans;
int main(){
scanf("%d%d%d%d",&t,&a,&s,&b);
while(a--) scanf("%d",&id),x[id]++;
for(int i=1;i<=t;i++) for(int j=b;j>=1;j--) for(int k=max(0,j-x[i]);k<=j-1;k++) dp[j]=(dp[j]+dp[k])%M;
for(int i=s;i<=b;i++) ans=(ans+dp[i])%M;
printf("%d\n",ans);
return 0;
}法二：利用本轮优化递推O(t*b)
如果我们按 j 从小到大顺序做 dp[i][j]
那么你可能会想，我可不可以用 dp[i][j-1] 更新 dp[i][j] 呢
dp[i][j-1] 讲道理再添一个数 就是 dp[i][j] 了
但是呢，你会发现他可能添不了，更新 dp[i][j-1] 包含正好用掉 cnt[i] 个的情况，那就没东西添了
然而你又发现，不就这一种情况吗。。无脑减掉就好了
于是转移方程如下
这时候因为顺序更新就不能降维了
而第一维 1e4 第二维 1e5 将导致 MLE，很简单的常用手段，第一维%2即可
那么代码如下
#include <cstdio>
#include <algorithm>
#define M 1000000
using namespace std;
int t,a,s,b,dp[2][100005],x[1005],id,ans;
int main(){
scanf("%d%d%d%d",&t,&a,&s,&b);
while(a--) scanf("%d",&id),x[id]++;
dp[0][0]=dp[1][0]=1;
for(int i=1;i<=t;i++) for(int j=1;j<=b;j++){
dp[i%2][j]=(dp[(i-1)%2][j]+dp[i%2][j-1])%M;
if(j-x[i]>=0) dp[i%2][j]=(dp[i%2][j]-dp[(i-1)%2][j-1-x[i]]+M)%M;
}
for(int i=s;i<=b;i++) ans=(ans+dp[t%2][i])%M;
printf("%d\n",ans);
return 0;
}然后的话，上面这两种写法也是可以继续优化的
这里，不用每次都跑到b
因为后面全是0嘛，每次你记录 m+=x[i]，然后跑到 min(m,b) 就行
然后的话下面还有个方法，好像目前没看到有人这么写的，我不具体讲，感兴趣的话可以看一下
和上面那个复杂度一样，但是这个dp记录的是直接是上面的dp的前缀和，写起来略微麻烦一点点
法三：直接前缀和dp(不具体讲了)O(t*b)
#include <cstdio>
#include <algorithm>
#define M 1000000
using namespace std;
int t,a,s,b,x[1005],dp[2][100005],id,am;
int main(){
scanf("%d%d%d%d",&t,&a,&s,&b);
while(a--) scanf("%d",&id),x[id]++;
for(int i=1;i<=t;i++){
int tmp=am+x[i],inc=0;
for(int j=1;j<=min(tmp,b);j++){
int st=max(0,j-x[i]-1),en=min(am,j-1);
inc=(inc+dp[(i-1)%2][en]-dp[(i-1)%2][st]+M)%M;
if(j-x[i]<=0) inc=(inc+1)%M;
if(j>am) dp[i%2][j]=(dp[(i-1)%2][am]+dp[(i-1)%2][j]+inc)%M;
else dp[i%2][j]=(dp[(i-1)%2][j]+inc)%M;
}
am=tmp;
}
printf("%d\n",(dp[t%2][b]-dp[t%2][s-1]+M)%M);
return 0;
}这个是我一开始的想法和写法，因为担心超时，所以没有分开写前缀和和dp值
事实上因为数据很水，就算时间复杂度翻成二倍也没事
但是上面这个思路确实很不错，毕竟是直接记录前缀和的dp直接更新，很厉害
下面这个比较正常的分开写，我懒得写了，直接上一个别人的代码
法四：记录dp前缀和优化dp更新O(t*b)
那么，这些代码其实都大同小异
但是很有学习价值
前缀和优化是很常用也很厉害的一种手段，这个要会
法二那个本轮转移也很强，想法很不错
这道题我觉得有必要好好掌握法二和法四