题目链接: 题意:给你n个数字,让这n个数字相加减,如果是360的倍数或者是0就输出YES,否则输出NO。 思路:二进制枚举每一种状态,或者直接暴力搜索。

二进制枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int maxn=4005,inf=1e8;
int a[maxn], n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 1; i < (1 << n); i++)
{
int sum = 0;
for(int j = 0; j < n; j++)
{
if(i & (1 << j)) sum += a[j];
else sum -= a[j];
}
if( !sum !(sum % 360)) return puts("YES"),0;
}
puts("NO");
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
const int maxn=4005,inf=1e8;
int a[maxn], n;
bool flag;
void dfs(int x, int sum)
{
if(x == n)
{
if(!(sum % 360)) flag = true;
return;
}
dfs(x + 1, sum + a[x]);
dfs(x + 1, sum - a[x]);
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
flag = false; dfs(0,0);
if(flag) puts("YES");
else puts("NO");
return 0;
}

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号