HDu 1160単純dp+ソート+逆シーケンス出力


まずマウスの構造体を定義し、マウスを先体重、後速度で並べ替え、並べ替えた後、体重が小さく速度が速いマウスを前に保証し、動的に計画するときは最長上昇シーケンスを求め、前駆体を記録するたびに再帰的に出力すればよい.
#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 ); }