DAG上の動的計画

長方形のネスト
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
長さと幅を表すn個の矩形があり、各矩形はa,bで記述することができる.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、aのみ
入力
1行目は正の数Nである(0試験データのグループ毎の1行目は正の数nであり、このグループの試験データに矩形の個数が含まれていることを示す(n<=1000)
次のn行は、各行に2つの数a,b(0 しゅつりょくテストデータのセットごとに1つの数を出力し、最大条件を満たす矩形の数を表し、各グループの出力は1行を占めます。 サンプル入力 1 10 1 2 2 4 5 8 6 10 7 9 3 1 5 8 12 10 9 7 2 2 サンプル出力 5
題意記述:n個の矩形があり、各矩形は2つの整数a、bで記述することができ、その長さと幅を表すことができる.
矩形(a,b)は、矩形(c,d)にネストすることができ、aのみ
できるだけ多くの矩形を1列に並べて、最後の1つを除いて、
各長方形は次の長方形にネストできます.複数の解がある場合は、長方形番号の辞書順はできるだけ小さくする必要があります.
解題構想:<1>矩形間のネスト可能な関係は「二元関係」であり、二元関係は図でモデリングすることができる.
矩形Xが矩形Yにネスト可能であれば、XからYまで1本の有向辺(G[x][y]=1)が連なる.
この図は無環で、矩形が直接または間接的に自分の内部にネストできないため、
言い換えれば、彼はDAGです.
これにより,原問題はDAG上の最長経路を求めることに転化する.
<2>では、DAGの最長パスをどのように求めますか?
定義可能状態:dp[i]は、ノードiから到達可能な最長経路の長さを表す
では、dp[i]=max(dp[j])+1であり、G[i][j]=1、すなわちiはjにネスト可能である
最後の配列dの最大値が結果である
<3>最小辞書シーケンスをどのように保証しますか?
すべてのdが算出された後、最大のd[i]に対応するiを選択する.
複数のiがある場合は、最小のiを選択します.(iが最初の始点)
次に、d[i]=d[j]+1、および(i,j)がエッジセットのいずれかのjを選択することができる.
ただし、辞書順が最小であることを保証するためには、その中の最小のjを選択すべきである.

#include 
#include 
#include 
using namespace std;

const int MAXN=1005;
int T,N;
int len[MAXN],wid[MAXN];
int G[MAXN][MAXN];
int d[MAXN],best=-(1<<30);
void build()	//  
{
	for(int i=0;i0)
		return ans;
	ans=1;
	for(int j=0;j>T;
	while(T--)
	{
		memset(G,0,sizeof(G));
		memset(d,-1,sizeof(d));
		best=-(1<<30);
		int n;
		cin>>n;
		N=n;
		int i=0;
		while(n--)
		{
			int a,b;
			cin>>a>>b;
			if(b>a)
				swap(a,b);
			len[i]=a;
			wid[i]=b;
			++i;
			
		}
		build();
		for(int i=0;i