HDU 1160 FatMouses Speed

[cpp] 
/**
*   Author : johnsondu
*   time : 2013-4-7
*   Type: DP, I want to really understand it
*   problem: FatMouse's Speed
*   url: http://acm.hdu.edu.cn/showproblem.php?pid=1160
*/ 
 
#include <iostream>  
#include <cstdio>  
#include <cmath>  
#include <vector>  
#include <cstring>  
#include <algorithm>  
using namespace std ; 
 
#define max(a, b) (a > b ? a : b)  
struct Node 
{ 
    int w, s ; 
    int idx ; 
}node[1005] ; 
int n, dp[1005] ; 
 
bool cmp (const Node &a, const Node &b) 
{ 
    if (a.w != b.w) 
        return a.w < b.w ; 
    return a.s > b.s ; 
} 
 
int main () 
{ 
    int i, j ; 
    //freopen ("data.txt", "r", stdin) ;  
    n = 0 ; 
    while (scanf ("%d%d", &node[n].w, &node[n].s) != EOF) 
    { 
        node[n].idx = n ; 
        n ++ ; 
    } 
    sort (node, node + n, cmp) ; 
 
    for (i = 0; i < n; i ++) 
        dp[i] = 1 ; 
 
    int num = 0 ; 
    for (i = 0; i < n-1; i ++) 
    { 
        for (j = i+1; j < n; j ++) 
            if (node[j].w > node[i].w && node[j].s < node[i].s) 
            { 
                dp[j] = max(dp[i]+1, dp[j]) ;           //狀態轉移方程  
                if (dp[j] > dp[num]) 
                    num = j ;                           //記錄最大值下標  
            } 
    } 
    printf ("%d\n", dp[num]) ; 
    int tp = num ; 
    vector<int> mm ; 
    mm.push_back(num) ; 
    for (i = num-1; i >= 0; i --)   //尋找路徑  
        if (dp[num] == dp[i] + 1) 
        { 
            mm.push_back(i) ; 
            num = i ; 
        } 
    for (i = dp[tp]-1; i >= 0; i --) 
        printf ("%d\n", node[mm[i]].idx+1) ; 
 
    return 0 ; 
}