You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ consisting of positive integers, and integers $x$ and $y$.Problem Statement
Determine whether it is possible to place $N+1$ points $p_1, p_2, \dots, p_N, p_{N+1}$ in the $xy$-coordinate plane to satisfy all of the following conditions. (It is allowed to place two or more points at the same coordinates.)
Constraints
Input
The input is given from Standard Input in the following format:
$N$ $x$ $y$ $A_1$ $A_2$ $\dots$ $A_N$
Output
If it is possible to place $p_1, p_2, \dots, p_N, p_{N+1}$ to satisfy all of the conditions in the Problem Statement, print Yes; otherwise, print No.
Sample Input 1
3 -1 1 2 1 3
Sample Output 1
Yes
The figure below shows a placement where $p_1 = (0, 0)$, $p_2 = (2, 0)$, $p_3 = (2, 1)$, and $p_4 = (-1, 1)$. All conditions in the Problem Statement are satisfied.
Sample Input 2
5 2 0 2 2 2 2 2
Sample Output 2
Yes
Letting $p_1 = (0, 0)$, $p_2 = (2, 0)$, $p_3 = (2, 2)$, $p_4 = (0, 2)$, $p_5 = (0, 0)$, and $p_6 = (2, 0)$ satisfies all the conditions. Note that multiple points may be placed at the same coordinates.
Sample Input 3
4 5 5 1 2 3 4
Sample Output 3
No
Sample Input 4
3 2 7 2 7 4
Sample Output 4
No
Sample Input 5
10 8 -7 6 10 4 1 5 9 8 6 5 1
Sample Output 5
Yes
首先考虑将 \(x\) 坐标和 \(y\) 坐标分开考虑，很明显他们是互不干扰的。然后可以用一个类似背包的方法计算。负数存在数组时可以通过加一个值计算。其实此题应该是可以 bitset 优化的（不过我没写）。注意 \(p2=(A1,0)\)
#include<bits/stdc++.h>
const int N=1005,M=2e4+5,T=1e4;
int n,x,y,dp[N][M],a[N],b[N],p,q,u;
int solve(int a[],int n,int x,int t)
{
memset(dp,0,sizeof(dp));
int st;
if(!t)
dp[1][a[1]+T]=1,st=2;
else
dp[0][T]=1,st=1;
for(int i=st;i<=n;i++)
{
for(int j=0;j<M;j++)
{
if(j>=a[i])
dp[i][j]=dp[i-1][j-a[i]];
if(j+a[i]<M)
dp[i][j]|=dp[i-1][j+a[i]];
}
}
// printf("%d\n",dp[n][x]);
return dp[n][T+x];
}
int main()
{
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=n;i++)
{
scanf("%d",&u);
if(i&1)
a[++p]=u;
else
b[++q]=u;
}
if(solve(a,p,x,0)&&solve(b,q,y,1))
printf("Yes");
else
printf("No");
}