ABC274D

date: 2022-10-23

%%
今年第一次打AT，切5题
之后就没时间了

G是原题，没时间贺了
%%

[[set]] [[DP]]

link: D - Robot Arms 2

xy轴分开考虑，考虑两个相似的DP

数据波动小（1~10），看起来状态数很少，所以直接上了set表示状态，可以自动去重，还不会爆空间
理论上极端数据会炸复杂度，但是它过了

赛时代码：

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,x,y,a[N],b[N],ca,cb;
set<int>A[N],B[N];
int main(){
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<=n;i++){																																					
		if(i&1)scanf("%d",&a[++ca]);
		else scanf("%d",&b[++cb]);
	}
	A[0].insert(0);B[0].insert(0);
	for(int i=1;i<=ca;i++){
		for(auto _:A[i-1]){
			A[i].insert(_+a[i]);
			if(i!=1)A[i].insert(_-a[i]);
		}
	}
	for(int i=1;i<=cb;i++){
		for(auto _:B[i-1]){
			B[i].insert(_+b[i]);
			B[i].insert(_-b[i]);
		}
	}
	if(A[ca].find(x)!=A[ca].end()&&B[cb].find(y)!=B[cb].end())printf("Yes");
	else printf("No"); 
}