题意:给出T种数字(1~T)。每种各有N[i]个。然后用这些数字构成的元素数量在a~b之间的组合数之和。
例如全集={1, 1, 2, 2, 3},即数字1和2出现两次,数字3出现1次。
那么元素数量为1的组合有3种: {1} {2} {3}
元素数量为2的组合有5种: {1,1} {1,2} {1,3} {2,2} {2,3}
元素数量为3的组合有5种: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
元素数量为4的组合有3种: {1,2,2,3} {1,1,2,2} {1,1,2,3}
元素数量为5的组合有1种: {1,1,2,2,3}
思路:动态规划。dp[i][j]表示用1~i这些数字,元素数量为j的个数。那么对每个dp[i][j],枚举数字i出现的次数即可求。复杂度为T*N(每种数字出现的最多次数,为100)*A(元素数量的上界)。这个地方可以优化到T*A,维护一个部分和即可。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s))
#define N 100005
int dp[2][N],s[1005];
int n,m,be,en;
int main(){
int i,j,now,a,b,res=0;
scanf("%d %d %d %d",&n,&m,&be,&en);
memset(s,0,(n+1)*sizeof(int));
for(i = 0;i<m;i++){
scanf("%d",&j);
s[j]++;
}
dp[0][0] = 1;
a = 1;
b = 0;
for(i = 1;i<=n;i++){
a = 1-a;
b = 1-b;
dp[b][0] = now = 1;//now是部分和
for(j = 1;j<=en;j++){
if(j<=s[i])
now += dp[a][j];
else
now += dp[a][j]-dp[a][j-s[i]-1]+1000000;
now %= 1000000;
dp[b][j] = now;
}
}
for(j = be;j<=en;j++){
res += dp[b][j];
res %= 1000000;
}
printf("%d\n",res);
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁