指针

前言：祝大家新年快乐哦！ヽ(✿ﾟ▽ﾟ)ノ

题目来源

今天的这道题来自于acwing的一道周赛题，链接如下：

4498. 指针 - AcWing题库

下面给出该题的题面

原题题面

给定一个如下图所示的全圆量角器。

初始时，量角器上的指针指向刻度 0。

现在，请你对指针进行 n 次拨动操作，每次操作给定一个拨动角度 ai，由你将指针拨动 ai 度，每次的拨动方向（顺时针或逆时针）由你自由决定。

请你判断，能否通过合理选择每次拨动的方向，使得指针最终仍然指向刻度 0

输入格式

第一行包含整数 n

接下来 n 行，每行包含一个整数 ai，表示一次操作的拨动角度。

输出格式

如果可以做到指针最终仍然指向刻度 0，则输出 YES，否则输出 NO。

数据范围
所有测试点满足 1 ≤ n ≤ 15，1 ≤ ai ≤ 180

输入样例1：

输出样例1：

YES

输入样例2：

输出样例2：

NO

输入样例3：

输出样例3：

YES

题目解释

优化思路

通过一系列的分析，我们可以大致得到一个思路，就是我们要灵活的计算出一个有效的方式，使得我们尽可能地使得我们的指针可以走回到0度或者说360度，不过吧，其实这道题和背包问题的一般思路是一样的，都分为取和不取，在背包问题里面，取和不取来分析在目前体积下可以达到的最大价值，而这道题就有些不同了，这道题是分为正向和反向，正向就当成取，反向就当成不取，因此我们可以同背包一样开一个二维数组，然后对于每一个方向都进行分析

首先，我们按照题目要求进行输入输出

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N][361], v[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> v[i];
}

其次，我们对于f数组进行一个判断

//原点一定是对的，记为1
f[0][0] = 1;
for(int i = 1;i <= n;i++)
    for(int j = 0;j <= 360;j++) 
        //正向取和反向取，满足一个就为1
        f[i][j] = f[i - 1][(j + 360 + v[i]) % 360] || f[i - 1][(j + 360 - v[i]) % 360];

最后，我们按照题目要求输出结果

//360取模和0是一样的，所以这两个都可以
if(f[n][0] == 1 || f[n][360] == 1) cout << "YES" << endl;
//反之不行
else cout << "NO" << endl;
return 0;

如此一来，我们就解决这道题目啦！下面给出ac代码

`ac`代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][360], v[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> v[i];
    f[0][0] = 1;
    for(int i = 1;i <= n;i++)
        for(int j = 0;j <= 360;j++)
            f[i][j] = f[i - 1][(j + 360 + v[i]) % 360] || f[i - 1][(j + 360 - v[i]) % 360];
    if(f[n][0] == 1 || f[n][360] == 1) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}