md,为什么啊!
查看原帖
md,为什么啊!
1368093
J_y_AC_t_k楼主2024/9/13 22:50

如图,受不了一点qwq:

求大佬邦邦qwq。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define lowbit(x) (x&(-x))
#define ADD 1800
inline int read(){
	int rt=0;	bool kk=0;	char g=getchar();
	while(g<'0'||g>'9')	kk|=(g=='-'),g=getchar();
	while(g>='0'&&g<='9')	rt=(rt<<3)+(rt<<1)+g-'0',g=getchar();
	return (kk?-rt:rt);
}
int n,ex,ey,tot,sum,st,D;
int d[2005];
bool do1[2005],do2[2005];
int f[2005][3605];
struct node{int r,w;}lst[2005][3605];
inline bool work(int m,bool ans[])
{
	if(((m+tot)&1)||(m+tot<0))	return 0;
	if(m==tot){memset(ans,1,(n+1));return 1;}
	if(m==-tot)	return 1;
	memset(f,0,sizeof(f));
	memset(lst,0,sizeof(lst));
	
	(m+=tot)>>=1,sum=0;
	for(st=1;st<=n;st++)	if(sum+d[st]<=m)	sum+=d[st];	else break;
	st--,f[st][sum-m+ADD]=st+1;
	for(int r=st+1;r<=n;r++)
	{
		for(int w=-D+ADD;w<=D+ADD;w++)	f[r][w]=f[r-1][w],lst[r][w]={r-1,w};
		for(int w=-D+ADD;w<=ADD;w++)
			if(f[r-1][w]>f[r][w+d[r]])
				f[r][w+d[r]]=f[r-1][w],lst[r][w+d[r]]={r-1,w};
		for(int w=D+ADD;w>=1+ADD;w--)
			for(int l=f[r-1][w]+1;l<f[r][w];l++)
				if(f[r][w-d[l]]<l)	f[r][w-d[l]]=l,lst[r][w-d[l]]={r,w};
	}
	if(f[n][ADD]>0)
	{
		for(int i=1;i<=st;i++)	ans[i]=1;
		node now={n,ADD};
		while(now.r>st)
		{
			node &A=lst[now.r][now.w];
			if(A.w<now.w)	ans[now.r]=1;
			else if(A.w>now.w)	ans[f[now.r][now.w]]=0;
			now=A;
		}
		return 1;
	}
	else return 0;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),ex=read(),ey=read();
	for(int i=1;i<=n;i++)	D=max(D,d[i]=read()),tot+=d[i];
	if(work(ex+ey,do1)&&work(ex-ey,do2))
	{
		puts("Yes");
		for(int i=1;i<=n;i++)
			if(do1[i]==do2[i])	putchar(do1[i]?'R':'L');
			else	putchar(do1[i]?'U':'D');
	}
	else puts("No");
	return 0;
}
2024/9/13 22:50
加载中...