最近被逼的不行了，所以動(dòng)真格的學(xué)動(dòng)規(guī)！先是把《程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐》這本書(shū)里動(dòng)規(guī)的例題都看過(guò)、做過(guò)，本來(lái)想一道一道的做習(xí)題的，結(jié)果poj掛了。于是轉(zhuǎn)戰(zhàn)hdu，昨天做了一道三維樹(shù)狀數(shù)組，比較理解了，今天又繼續(xù)hdu的動(dòng)規(guī)，感覺(jué)做過(guò)的題型，換個(gè)背景再做能夠想到并且實(shí)現(xiàn)了，細(xì)節(jié)上還需注意。
hdu 1160 FatMouse's Speed
題目大意：
給定n只老鼠的體重w和速度s，求一個(gè)最長(zhǎng)的排列，使得這個(gè)排列中的老鼠體重嚴(yán)格遞增，速度嚴(yán)格遞減。題目看上去很像最長(zhǎng)上升子序列，只是這里的序列是可以打亂順序按體重排序的。
解題思路：
整體思路同最長(zhǎng)上升子序列。
1、按老鼠的體重遞增排序，當(dāng)老鼠的體重相等時(shí)按速度遞減排序。
2、f[j]表示前j只老鼠中最長(zhǎng)序列的長(zhǎng)度，狀態(tài)轉(zhuǎn)移方程為
f[N]初始值為0；
f[j]=max{ f[i] : 0<=i<j 且 s[j]<s[i] }+1;
也就是說(shuō)，如果第j只老鼠是最長(zhǎng)序列中的話，那么它肯定比上一個(gè)在最長(zhǎng)序列中老鼠體重更大 ( 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;
}