P7774 [COCI 2009-2010 #2] KUTEVI

pengzy___ · 2021-10-31 18:23:22 · 题解

题目传送门

有 m 个数，这 m 个数能否由另外 n 个数通过加减运算获得。对于每一次加减的操作，结果不能小于 0 ，对于大于等于 360 的结果，对 360 取模。

此题可以用搜索和动态规划做，这里是完全背包的做法。注意在做的过程中要 mod 360 。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[15],b[15],f[1005];
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];
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=1000;j++)
        {
            if(j>=a[i])
            f[j%360]|=f[(j-a[i])%360];
            f[j%360]|=f[(j+a[i])%360];
        }
    for(int i=1;i<=m;i++)
    {
        if(f[b[i]]==1)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}