1 条题解

  • 0
    @ 2026-7-5 0:14:29

    #include <cstdio>
    #include <bitset>
    #include <iostream>
    using namespace std;
    const int M = 2001;
    int read()
    {
    	int x=0,f=1;char c;
    	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
    	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    	return x*f;
    }
    int n,m[2],a[M],x,y,sum;
    bitset<3600001> dp[M];string ans;
    int Abs(int x) {return x>0?x:-x;}
    signed main()
    {
    	n=read();x=read();y=read();
    	m[0]=x-y;m[1]=x+y;
    	for(int i=0;i<n;i++) sum+=a[i]=read();
    	for(int i=0;i<2;i++)
    		if(Abs(m[i])>sum) {puts("No");return 0;}
    	for(int i=0;i<2;i++)
    	{
    		if((m[i]+sum)%2) {puts("No");return 0;}
    		else m[i]=(m[i]+sum)/2;
    	}
    	dp[0][0]=1;
    	for(int i=0;i<n;i++) dp[i+1]=dp[i]|(dp[i]<<a[i]);
    	if(!dp[n][m[0]] || !dp[n][m[1]])
    		{puts("No");return 0;}
    	for(int i=n-1;i>=0;i--)
    	{
    		int x=0;
    		for(int j=0;j<2;j++)
    			if(!dp[i][m[j]])//must decrease
    			{
    				m[j]-=a[i];
    				x+=(1<<j);
    			}
    		if(x==0) ans='L'+ans;
    		if(x==1) ans='D'+ans;
    		if(x==2) ans='U'+ans;
    		if(x==3) ans='R'+ans;
    	}
    	puts("Yes");
    	cout<<ans<<endl;
    }
    
    
    • 1

    信息

    ID
    12245
    时间
    5000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者