虽然这个题想通过不难,但还是值得记录
题意:
题目描述
给定 N 个角(第 i 个角记作 ai ),作为初始角,另给定 M 个角(第 i 个角记作 bi),作为目标角。
请求出对于每个 bi,它是否能被若干个 ai之间的加、减运算得到。
注意同一个 ai可以用多次,也可以不用。
输入格式
第一行两个正整数 N,M
第二行 N 个正整数,第 i 个数为 ai
第三行 M 个正整数,第 i 个数为 bi
输出格式
共 M 行,在第 i 行,如果 bi能被若干个 ai之间的加、减运算得到,输出YES,否则输出NO。
输入
2 1
30 70
40
输出
YES
输入
1 1
100
60
输出
YES //15×100 ∘=1500 ∘ =60 ∘
1、完全背包
重点是转化出这个想法:
你和另一个人都有 n 种物品,每种物品有无数个。你可以将这些物品卖出,也可以买进。判断可否通过买卖这n种物品,使你得到 m块钱。
这样就像是背包了
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<=1005;j++){if(j>=a[i]) f[j%360]=max(f[(j-a[i])%360],f[j%360]);//a[i]取或者不取f[j%360]=max(f[(j+a[i])%360],f[j%360]);}
}
for(int i=1;i<=m;i++)
{if(f[b[i]]==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}
2、普通做法(因为数据少,所以可行)
把每一个a中的角度都加上他的1-359倍,即把所有情况都存下来(同时取模)
若此时所有情况中有bi,则可以表示
凭感觉,过了,但就是解释不清,重点是上面的完全背包,这个仅供娱乐,所以要勇于尝试?
cin>>n>>m;
x=0;
for(int i=1;i<=n;i++)
{cin>>a[i];for(int j=1;j<=359;j++){f[x++]=a[i]*j%360;}
}
k=0;
for(int i=1;i<=m;i++)
{cin>>b[i];k=0;for(int j=0;j<x;j++){if(b[i]==f[j]) {cout<<"YES"<<endl;k=1;break;}}if(k==0) cout<<"NO"<<endl;
}