没过数据求助
查看原帖
没过数据求助
648660
Name1楼主2022/7/28 15:53

找不到问题

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n,m,ans,dp[N][N];
struct node
{
	int x,p,id;
	bool operator <(const node &a)const{return a.x>x;}
}a[N];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i].x=read(),a[i].p=read(),a[i].id=i;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++) printf("%d ",a[i].x);
	puts("");
	for(int i=1;i<=n;i++)
	{
		dp[i][i]=a[i].p;
		for(int j=i+1,now=i+1;j<=n;j++)
		{
			dp[i][j]=dp[i][j-1]-a[j-1].p;
			while(now>1&&a[j].x-a[i].x>=a[i].x-a[now-1].x)
				dp[i][j]=max(dp[i][j],dp[--now][j]);
			dp[i][j]+=a[i].p;
			ans=max(ans,dp[i][j]);
		}
	}
	for(int i=n;i>=1;i--)
	{
		dp[i][i]=a[i].p;
		for(int j=i-1,now=i-1;j>=1;j--)
		{
			dp[i][j]=dp[i][j+1]-a[j+1].p;
			while(now<n&&a[i].x-a[j].x>=a[now+1].x-a[i].x)
				dp[i][j]=max(dp[i][j],dp[++now][j]);
			dp[i][j]+=a[i].p;
			ans=max(ans,dp[i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}
/*
6 
5 6 
1 1 
10 5 
7 6 
4 8 
8 10 
*/
2022/7/28 15:53
加载中...