HDu 1160単純dp+ソート+逆シーケンス出力
1693 ワード
まずマウスの構造体を定義し、マウスを先体重、後速度で並べ替え、並べ替えた後、体重が小さく速度が速いマウスを前に保証し、動的に計画するときは最長上昇シーケンスを求め、前駆体を記録するたびに再帰的に出力すればよい.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 1007
using namespace std;
struct Mice
{
int w,s,id;
bool operator < ( const Mice & a ) const
{
return w < a.w;
if ( w == a.w ) return s > a.s;
}
}m[MAX];
int dp[MAX];
int pre[MAX];
void print ( int maxn )
{
if ( maxn == 0 ) return;
print ( pre[maxn] );
printf ( "%d
" , m[maxn].id );
}
int main ( )
{
int cnt = 1;
while ( ~scanf ( "%d%d" , &m[cnt].w , &m[cnt].s ) )
{
// cout << m[cnt].w << " " << m[cnt].s << endl;
m[cnt].id = cnt;
cnt++;
}
memset ( dp , 0 , sizeof ( dp ) );
sort ( m+1 , m+cnt );
/* cout << "**************************" << endl;
for ( int i = 1 ; i < cnt ; i++ )
cout << m[i].w << " " << m[i].s << endl;
cout << "**************************" << endl;*/
m[0].w = 0 ,m[0].s = 99999999;
int maxn = 0;
for ( int i = 1 ; i < cnt ; i++ )
for ( int j = 0 ; j < i ; j++ )
if ( m[i].w > m[j].w && m[i].s < m[j].s )
if ( dp[j] + 1 > dp[i] )
{
dp[i] = dp[j] + 1;
pre[i] = j;
if ( dp[i] > dp[maxn] )
maxn = i;
}
printf ( "%d
" , dp[maxn] );
print ( maxn );
}