最近被逼的不行了，所以动真格的学动规！先是把《程序设计导引及在线实践》这本书里动规的例题都看过、做过，本来想一道一道的做习题的，结果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;
}