怎样建设有价值的网站,南宁公司网站开发,湖州网站建站,鸿蒙开发语言题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/696/D 来源#xff1a;牛客网
小K有n个雕塑#xff0c;每个雕塑上有一个整数 若集合T中的每一个元素在n个雕塑上都能找得到#xff0c;则称这个集合为一个优秀的集合
小K想知道所有大小k优秀…题干
链接https://ac.nowcoder.com/acm/contest/696/D 来源牛客网
小K有n个雕塑每个雕塑上有一个整数 若集合T中的每一个元素在n个雕塑上都能找得到则称这个集合为一个优秀的集合
小K想知道所有大小k优秀的集合的价值和是多少
一个优秀的集合的价值可以用来表示 输入描述:
两个整数n,k分别表示雕塑的数量与集合大小的上限
接下来n个整数表示第i个雕塑上的数字aiai是多少
输出描述:
一行表示所有大小k优秀集合的权值和
示例1
输入
复制
3 0
1 2 3
输出
复制
1
示例2
输入
复制
3 1
1 2 3
输出
复制
7
示例3
输入
复制
3 2
1 2 3
输出
复制
18
示例4
输入
复制
3 3
1 2 3
输出
复制
24
示例5
输入
复制
8 1
1 6 35 45 65 3 56 8
输出
复制
220
备注: 有10%10%的数据满足k1
有30%30%的数据满足kn
以上两个部分包含在100%100%的数据中但不包含在前30%30%的数据中
对于前30%30%的数据满足k≤n≤5k≤n≤5
对于100%100%的数据满足n≤106,1≤ai≤5×103n≤106,1≤ai≤5×103
由于答案可能过大请对1097取模后输出
解题报告 题意好难懂啊、、、 注意到集合的性质互异性。
根据鸽巢原理很容易知道最多有m5e3个数去重之后
然后设F[n][k]表示前n个数取k个数的价值。且已知这k个数一定互不相同。因为集合的互异性 F[n][k]F[n-1][k]F[n-1][k-1]*a[i]
效率O(m^2)。
当然这题也可以用01背包的方法将空间复杂度优化到一维。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 1e6 5;
const ll mod 1e97;
ll dp[5005][5005];
int a[MAX],b[MAX];
int n,k;
int main()
{cinnk;for(int i 1; in; i) cina[i],b[i]a[i];sort(b1,bn1);int N unique(b1,bn1) - b - 1;dp[0][0]1;for(int i 1; iN; i) {dp[i][0] 1;for(int j 1; jk; j) {dp[i][j] (dp[i-1][j] dp[i-1][j-1] * b[i])%mod;}}ll ans 0;for(int i 0; iN ik; i) ans (ans dp[N][i])%mod;cout ans endl;return 0 ;
}
