73pts求助 WA#3 #4 #7,不知道错在哪
查看原帖
73pts求助 WA#3 #4 #7,不知道错在哪
585805
MCRS_lizi楼主2022/3/8 21:34
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,xs,l,r,dp[2001][2001][3],f[2001][2001][3];

struct sb
{
	int x,y,v;
}a[10001];
bool cmp(sb v,sb u)
{
	return v.x<u.x;
}
int max(int u,int v)
{
    return u>v? u:v;
}
int min(int u,int v)
{
    return u<v? u:v;
}
signed main()
{
	cin>>n>>xs;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].y;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].v;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i].x>xs)
		{
			r=i;
			l=i-1;
			break;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j][1]=-1e18;
			dp[i][j][2]=-1e18;
		}
	}
	f[l][l][1]=f[l][l][2]=xs-a[l].x;
	f[r][r][1]=f[r][r][2]=a[r].x-xs;
	dp[l][l][1]=dp[l][l][2]=a[l].y-f[l][l][1]*a[l].v;
	dp[r][r][1]=dp[r][r][2]=a[r].y-f[r][r][1]*a[r].v;
//	cout<<dp[l][l][1]<<"/"<<dp[l][l][2]<<" "<<dp[r][r][1]<<"/"<<dp[r][r][2]<<endl;
//	cout<<l<<" "<<r<<endl<<endl;
	for(int i=2;i<=n;i++)
	{
		int left=max(1,l-i+1),right=min(r,n-i+1);
		for(int j=left;j<=right;j++)
		{
			if(1)
			{
				if(dp[j+1][j+i-1][1]+a[j].y-(f[j+1][j+i-1][1]+a[j+1].x-a[j].x)*a[j].v>dp[j+1][j+i-1][2]+a[j].y-(f[j+1][j+i-1][2]+a[j+i-1].x-a[j].x)*a[j].v)
				{
					dp[j][j+i-1][1]=dp[j+1][j+i-1][1]+a[j].y-(f[j+1][j+i-1][1]+a[j+1].x-a[j].x)*a[j].v;
					f[j][j+i-1][1]=f[j+1][j+i-1][1]+a[j+1].x-a[j].x;
				//	cout<<1<<" ";
				}
				else if(dp[j+1][j+i-1][1]+a[j].y-(f[j+1][j+i-1][1]+a[j+1].x-a[j].x)*a[j].v<dp[j+1][j+i-1][2]+a[j].y-(f[j+1][j+i-1][2]+a[j+i-1].x-a[j].x)*a[j].v)
				{
					dp[j][j+i-1][1]=dp[j+1][j+i-1][2]+a[j].y-(f[j+1][j+i-1][2]+a[j+i-1].x-a[j].x)*a[j].v;
					f[j][j+i-1][1]=f[j+1][j+i-1][2]+a[j+i-1].x-a[j].x;
				//	cout<<2<<" ";
				}
				else
				{
					dp[j][j+i-1][1]=dp[j+1][j+i-1][2]+a[j].y-(f[j+1][j+i-1][2]+a[j+i-1].x-a[j].x)*a[j].v;
					f[j][j+i-1][1]=min(f[j+1][j+i-1][2]+a[j+i-1].x-a[j].x,f[j+1][j+i-1][1]+a[j+1].x-a[j].x);
				//	cout<<3<<" "<<j+1<<" "<<j+i-1<<" ";
				}
			}
			if(j+i-1==l)
			{
				dp[j][j+i-1][1]=dp[j+1][j+i-1][1]+a[j].y-(f[j+1][j+i-1][1]+a[j+1].x-a[j].x)*a[j].v;
				f[j][j+i-1][1]=f[j+1][j+i-1][1]+a[j+1].x-a[j].x;
			}
			if(1)
			{
					if(dp[j][j+i-2][2]+a[j+i-1].y-(f[j][j+i-2][2]+a[j+i-1].x-a[j+i-2].x)*a[j+i-1].v>dp[j][j+i-2][1]+a[j+i-1].y-(f[j][j+i-2][1]+a[j+i-1].x-a[j].x)*a[j+i-1].v)
					{
						dp[j][j+i-1][2]=dp[j][j+i-2][2]+a[j+i-1].y-(f[j][j+i-2][2]+a[j+i-1].x-a[j+i-2].x)*a[j+i-1].v;
						f[j][j+i-1][2]=f[j][j+i-2][2]+a[j+i-1].x-a[j+i-2].x;
				//		cout<<1<<endl;
					}
					else if(dp[j][j+i-2][2]+a[j+i-1].y-(f[j][j+i-2][2]+a[j+i-1].x-a[j+i-2].x)*a[j+i-1].v<dp[j][j+i-2][1]+a[j+i-1].y-(f[j][j+i-2][1]+a[j+i-1].x-a[j].x)*a[j+i-1].v)
					{
						dp[j][j+i-1][2]=dp[j][j+i-2][1]+a[j+i-1].y-(f[j][j+i-2][1]+a[j+i-1].x-a[j].x)*a[j+i-1].v;
						f[j][j+i-1][2]=f[j][j+i-2][1]+a[j+i-1].x-a[j].x;
			//			cout<<2<<endl;
					}
					else
					{
						dp[j][j+i-1][2]=dp[j][j+i-2][1]+a[j+i-1].y-(f[j][j+i-2][1]+a[j+i-1].x-a[j].x)*a[j+i-1].v;
						f[j][j+i-1][2]=min(f[j][j+i-2][1]+a[j+i-1].x-a[j].x,f[j][j+i-2][2]+a[j+i-1].x-a[j+i-2].x);
				//		cout<<3<<endl;
					}
			}
			if(j==r)
			{
				dp[j][j+i-1][2]=dp[j][j+i-2][2]+a[j+i-1].y-(f[j][j+i-2][2]+a[j+i-1].x-a[j+i-2].x)*a[j+i-1].v;
				f[j][j+i-1][2]=f[j][j+i-2][2]+a[j+i-1].x-a[j+i-2].x;
			}
		//	cout<<dp[j][i+j-1][1]<<"/"<<dp[j][i+j-1][2]<<" "<<"****"<<f[j][i+j-1][1]<<"/"<<f[j][i+j-1][2]<<" ";
		}
	//	cout<<endl;
	}
	printf("%.3f",max(dp[1][n][1],dp[1][n][2])/1000.0);
	return 0;
}

有些奇奇怪怪的写法不用管,只是调试语句没删而已

2022/3/8 21:34
加载中...