上海计算机学会2022年6月月赛C++乙组T1子集和（四）
发布时间
阅读量：
阅读量
子集和（四）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
子集和问题是指，给定 n 个数字 a1,a2,⋯,an，再给定一个目标 t，有多少种方法，能够选出一些数字，使得它们的和等于 t。在这道题目中，每个数字可以重复使用任意多次。
小爱希望计算一些带有限制的子集和问题，她想知道，如果规定不能选择 ai，那么还有多少种方法，可以选出一些数字，使得它们的和等于目标 t？
输入格式
- 第一行：两个整数表示 n 与 t。
- 第二行：n 个整数表示 a1,a2,⋯,an；
- 输入数据保证对任意 𝑖≠𝑗 有 𝑎𝑖≠𝑎𝑗。
输出格式
共 n 行，每行一个数，表示有多少种方法，在禁止选择 ai 的条件下，子集和问题的答案。由于答案可能很大，输出方案数模 1,000,000,007 的余数。
数据范围
- 对于 30% 的数据，1≤n≤20；
- 对于 60% 的数据，1≤n≤300；
- 对于 100% 的数据，1≤n≤5000；
- 1≤ai≤10000；
- 1≤t≤10000；
样例数据
输入:
3 16
1 5 10
输出:
0
2
4
说明:
不用1不可能
不用5的方案为 116, 16+101
不用10的方案为 116, 111+51, 16+52, 11+53
解析：
完全背包的方案数计算，去掉至少含有一个ai的方案数即为答案，时间复杂度O(nt)。
详见代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,t;
int a[5005];
int dp[10005];
int ans;
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++){
cin>>a[i];
}
//求完全背包的方案数
dp[0]=1;//一个不用是一种方案
for(int i=1;i<=n;i++){//外循环顺序枚举n个数（完全背包）
for(int j=a[i];j<=t;j++){//前i个数组成j的方案数
dp[j]+=dp[j-a[i]];
dp[j]%=mod;
}
}
for(int i=1;i<=n;i++){//针对每个ai
if (t>=a[i]){//t大于等于a[i]，则a[i]有可能是t的组成部分
ans=dp[t]-dp[t-a[i]];//减掉至少含有一个ai的方案
}else{//若t<ai，则方案中不含有ai
ans=dp[t];
}
cout<<(ans+mod)%mod<<"\n";
}
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~