ouuan 的博客

ouuan 的博客

题解 CF1097B 【Petr and a Combination Lock】

posted on 2019-01-06 14:07:08 | under 题解 |

如果是在打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}$ 。

#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;
}