ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[Atcoder]ABC251 B - At Most 3 (Judge ver.) (DFS)

2022年5月15日 956点热度 0人点赞 0条评论

传送门:B - At Most 3 (Judge ver.) (atcoder.jp)

题目大意

给定一个长度为N的数组(N <= 300),每次从中取出至多3个数字,问所有可能的且小于等于W的和(sum)有多少种。

思路

dfs,一共3层,每层可能的结果为a[1 ~ N]或0(不选)。

为了防止重复选择,用vis数组防止重复,还可以用k(循环开始位置)来剪枝。

第二个剪枝就是当sum > W时直接退出,这时候已经不可能是答案了。

用一个bitset数组来记录下那些数字已经被加到答案中了,避免重复添加。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 310;
int a[maxn];
bitset<maxn * 10000> add;//表示已经被加到答案中 
bitset<maxn> vis;//表示这个位置的数字已经被选了 

int N, W;

int dfs(int u, int k, int sum)
{
	int res = 0;
	
	if(sum > W)return 0; //剪枝,返回一个零元 
	if(u == 4) //当已经选完了 3 层 
	{
		//确保每个结果只被加一次 
		if(0 < sum && sum <= W && !add[sum])return add[sum] = 1; //这里会返回 ,同时会给add[sum]赋值 
		return 0;
	}
	res += dfs(u + 1, k, sum); //这一层不选 
	for(int i = k;i <= N; ++ i) //从k开始循环,可以剪枝减少重复遍历 
	{
		if(!vis[i]) //只能选择未被选过的 
		{
			vis[i] = 1;
			res += dfs(u + 1, i + 1, sum + a[i]);
			vis[i] = 0;
		}
	}
	return res;
}

signed main()
{
	cin >> N >> W;
	for(int i = 1;i <= N; ++ i)scanf("%lld", a + i);
	cout << dfs(1, 1, 0) << '\n';
	return 0;
}

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: abc atcoder C++ dfs 算法 算法竞赛
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意
  • 思路
  • 代码

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号