题解 CF1097B 【Petr and a Combination Lock】
ouuan
2019-01-06 14:07:08
如果是在打CF的时候碰到这道题肯定是写个爆搜，但如果是赛后做题就可以考虑 $O(n)$（~~常数为360~~）做法。
$f_{i,j}$ 表示转 $i$ 次后是否有可能为 $j$ 度，$f_{0,0}=true,\ f_{i,j}=f_{i-1,(j+a_i)\mod 360}\ or\ f_{i-1,(j-a_i)\mod 360}$ 。
答案就是 $f_{n,0}$ 。
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int N=20;
const int M=360;
int n,a[N];
bool f[N][M];
int main()
{
int i,j;
cin>>n;
for (i=1;i<=n;++i) cin>>a[i];
f[0][0]=true;
for (i=1;i<=n;++i)
{
for (j=0;j<M;++j)
{
f[i][j]=(f[i-1][(j+a[i])%M]|f[i-1][((j-a[i])%M+M)%M]);
}
}
if (f[n][0]) puts("YES");
else puts("NO");
return 0;
}
```