POJ 2008優先キュー好題数形結合

この問題はやるときは断固としてできない.
一晩と午前中をしました.ACになってから、とても気持ちがいいです!
集合が与えられ、集合内の要素にはw,hの2つの属性がある.次の条件を満たすサブセットをこのセットから取り出します.
A*(H-h)+B*(W-w)<=C;
ここで、h,wは、サブセットを取り出すすべての要素の中で最も小さいhおよびwである.
サブセットの最大要素数を求めます.
素朴な方法は次のとおりです.
wとhを列挙して、条件に合致する点をカウントして、このようにO(n^3)のアルゴリズムは过ぎません...
分析:
1.不等式A*(H-h)+B*(W-w)<=C;w,hをxに置き換えると,yは二元一次方程式の線形計画特性を満たす.
2.サブセットの全ての点でH>h,W>w.を満たし、A*(H−h)+B*(W−w)<=Cである.これが(w,h)を直角頂点とする直角三角形である.
2つの直角の辺の長さはそれぞれC/A.C/A.で、そこで、テーマは平面点で集中して、このような三角形の枠で枠を囲んでいる最大点数に変わりました.
シンプルアルゴリズムの最適化:
w値を列挙し、hが単調な場合、斜辺も単調である.
では、h減算の順序でソートし、優先キューのルールが斜辺減算ソートであることを保証する.
イメージとしては,水平直角エッジで徐々に下に移動し,優先キューはポイントセットを維持する.
最大値を計算すればいいです.
数形結合しましょう!はっきり言って、この問題はとても簡単で、私はどうしてこんなに長い間やって、思考は厳格です!

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

struct node
{
 	   int w,h,v;
 	   friend bool operator<( node a,node b ){
	   		  return a.v<b.v;
	   }
}sh[1111];

bool cmp_h( node a,node b ){
 	 return a.h>b.h;
}

int main()
{
 	int n,a,b,c;
 	while( scanf("%d %d %d %d",&n,&a,&b,&c)!=EOF )
 	{
	 	   for( int i=0;i<n;i++ )
	 	   {
		   		scanf( "%d %d",&sh[i].h,&sh[i].w );
		   		sh[i].v=a*sh[i].h+b*sh[i].w;
		   }
		   priority_queue<node> PQ;
		   sort( sh,sh+n,cmp_h );
		   int ans=0;
		   for( int i=0;i<n;i++ )
		   {
		   		while( !PQ.empty() ) PQ.pop();
		   		int min_H=sh[i].h;
		   		int min_W=sh[i].w;
		   		for( int j=0;j<n;j++ )
		   		{
				 	 if( sh[i].v>min_H*a+min_W*b+c )
				 	 	 break;
				 	 if( sh[j].v<=min_H*a+min_W*b+c )
				 	 {
					  	 min_H=min(sh[j].h,min_H);
				 	 	 if( sh[j].w>=min_W )
				 	 	 	 PQ.push(sh[j]);
				 	 	 while( !PQ.empty() && PQ.top().v>min_H*a+min_W*b+c )
						  		PQ.pop();
					 }
					 ans=max(ans,(int)PQ.size());
 	 	 		}
   		   }
   		   printf( "%d
",ans );
  	}
 	return 0;
}