贪心骗了40分,不知道贪心错在哪,求助
查看原帖
贪心骗了40分,不知道贪心错在哪,求助
341864
sgxsz楼主2024/10/10 11:02
#include<bits/stdc++.h>
using namespace std;

inline int read(){
	register int x=0,ch=getchar();
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch<='9'&&ch>='0'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	return x;
}
#define int long long
int a[50004],b[50004];
struct dl{
	int a,b;
}q[50004];
inline int _max(int x,int y){ return x>y?x:y; }
inline int zd(int j,int i){
	int s=q[j].a*q[j].b;
	return _max(q[j].a,a[i])*_max(q[j].b,b[i])-s;
}
signed main()
{
	//freopen("P2900_2.in","r",stdin);
	register int n,i,j,t;
	cin>>n;
	for(i=1;i<=n;i++)	a[i]=read(),b[i]=read();
	
	int id,minn;
	q[t=1].a=a[1];  q[1].b=b[1];
	for(i=2;i<=n;i++){
		id=-1;	minn=a[i]*b[i];
		for(j=1;j<=t;j++)
			if(minn>=zd(j,i)){
				minn=zd(j,i);
				id=j;
			}
		if(id!=-1){
			q[id].a=_max(a[i],q[id].a);
			q[id].b=_max(b[i],q[id].b);
		}else{
			q[++t].a=a[i];
			q[t].b=b[i];
		}
	}
	int ans=0;
	for(i=1;i<=t;i++)	ans+=q[i].a*q[i].b;
	cout<<ans;
	return 0;
}
2024/10/10 11:02
加载中...