最近被逼的不行了，所以動真格的學動規！先是把《程序設計導引及在線實踐》這本書里動規的例題都看過、做過，本來想一道一道的做習題的，結果poj掛了。于是轉戰hdu，昨天做了一道三維樹狀數組，比較理解了，今天又繼續hdu的動規，感覺做過的題型，換個背景再做能夠想到并且實現了，細節上還需注意。
hdu 1160 FatMouse's Speed
題目大意：
給定n只老鼠的體重w和速度s，求一個最長的排列，使得這個排列中的老鼠體重嚴格遞增，速度嚴格遞減。題目看上去很像最長上升子序列，只是這里的序列是可以打亂順序按體重排序的。

解題思路：
整體思路同最長上升子序列。
1、按老鼠的體重遞增排序，當老鼠的體重相等時按速度遞減排序。
2、f[j]表示前j只老鼠中最長序列的長度，狀態轉移方程為
      f[N]初始值為0；
      f[j]=max{ f[i] : 0<=i<j 且 s[j]<s[i] }+1;
      也就是說，如果第j只老鼠是最長序列中的話，那么它肯定比上一個在最長序列中老鼠體重更大 ( j>i ) 且速度更小 ( s[j] < s[i] )。

代碼如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int N = 1010;
struct Mouse{
    int w, s, num;
}m[N];
int f[N], pre[N];
bool cmp(Mouse a, Mouse b){
    if(a.w<b.w)
        return true;
    else if (a.w==b.w)
        return a.s>b.s;
    return false;
}
int main(){
    int i=0,n=0;
    while(scanf("%d %d", &m[n].w, &m[n].s)!=EOF){
        m[n].num=n+1;
        n++;
    }
    sort(m, m+n, cmp);
    memset(f, 0, sizeof(f));
    memset(pre, -1, sizeof(pre));
    int mx=0,end=0;
    for(i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(m[i].s<m[j].s && m[i].w>m[j].w){
                if(f[j]+1>f[i]){
                    f[i]=f[j]+1;
                    pre[i]=j;
                }
            }
        }
        if(f[i]>mx){
            mx=f[i];
            end=i;
        }
    }
    printf("%d\n", mx+1);
    int ans[N], len=0, x;
    x=end; ans[0]=x;
    while(pre[x]>=0){
        ans[++len]=pre[x];
        x=pre[x];
        if(x<0) break;
    }
    for(i=len; i>=0; i--)
        printf("%d\n", m[ans[i]].num);
    return 0;
}