这是一道较为简单的可行性DP。
首先看到题目，很容易想到将横纵坐标一起进行处理，但显然时间会炸飞。
所以我们将横纵坐标拆开分别处理，那么就有如下状态：
\(dpa_{i,j}\) 表示在所有竖直移动的操作中，进行到第 \(i\) 个时能否到达 \(j\)。
\(dpb_{i,j}\) 表示在所有水平移动的操作中，进行到第 \(i\) 个时能否到达 \(j\)。
那么转移方程很显然：
\[\begin{cases}dpa_{i,j}=dpa_{i-1,j-a_i}|dpa_{i-1,j+a_i}\\dpb_{i,j}=dpb_{i-1,j-a_i}|dpb_{i-1,j+a_i}\end{cases} \]然后就做完了。
Code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
// char buf[1<<21],*p1=buf,*p2=buf;
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
int n,x,y;
int a[MAXN],b[MAXN];
int cnta,cntb;
int dpa[2005][20005],dpb[2005][20005];
int main()
{
n=read(),x=read()+10000,y=read()+10000;
for(int i=1;i<=n;i++)
{
int x=read();
if(i%2==0) a[++cnta]=x;
else b[++cntb]=x;
}
dpa[0][10000]=true;
for(int i=1;i<=cnta;i++)
for(int j=a[i];j<=20000;j++)
dpa[i][j]=dpa[i-1][j-a[i]]|dpa[i-1][j+a[i]];
dpb[1][b[1]+10000]=true;
for(int i=2;i<=cntb;i++)
for(int j=b[i];j<=20000;j++)
dpb[i][j]=dpb[i-1][j-b[i]]|dpb[i-1][j+b[i]];
if(dpa[cnta][y] && dpb[cntb][x]) printf("Yes\n");
else printf("No\n");
return 0;
}