P7774

Astatinear · 2021-08-03 15:54:31 · 题解

题目传送门

思路

背包问题。

我们假设 dp_j 表示是否能够达到 j 度这个角度,如果可以, dp_j=1 ,如果不可以, dp_j=0。

首先,初始值: dp_0=1。

然后,我们来看 dp_j 的状态转移。

两种情况:

一:如果我们选择了 +a_i ,则状态转移为 dp_j \gets dp_j | dp_{j - a_i}。

二:如果选择了 -a_i ,则状态转移为 dp_j \gets dp_j | dp_{j + a_i}。

注意事项:

一:由于这是完全背包,所以 j 这一层循环要正着枚举。

二:由于所有角度均小于 360 度,所以状态转移要改成 dp_{j \bmod 360} \gets dp_{j \bmod 360} | dp_{(j-a_i) \bmod 360}。

答案

如果 dp_{b_i}=1 ,输出\text{yes}。

如果 dp_{b_i}=0 ,输出\text{no}。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[15],b[15];
int dp[1005];//dp数组
int main()
{
    //输入
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    cin>>a[i];
    for(int i=1;i<=m;++i)
    cin>>b[i];
    dp[0]=1;//初始值,dp[0]=1
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=1000;++j)//由于是完全背包,j枚举大一点
        {
            //状态转移
            if(j>=a[i])
            dp[j%360]|=dp[(j-a[i])%360];
            dp[j%360]|=dp[(j+a[i])%360];
        }
    }
    for(int i=1;i<=m;++i)
    {
        //判断输出YES,还是NO
        if(dp[b[i]]==1)
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
    }
}