无知 无求

0%

hdu1160 FatMouse's Speed

发表于 分类于 ，

题意

给n个老鼠，有各自的重量和速度，要找到一个体重严格上升，速度严格下降的最长排列

题解

实际就是LIS 条件变一下，我用了一个之前图的思路来求 也勉强算是记忆化搜索吧。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int W[1020],S[1020],length[1020],nextm[1020];
vector<int> G[1020];
bool find_mat(int a,int b){
    return W[a]>W[b]&&S[a]<S[b];
}
int dfs(int x){
    if(length[x]!=-1){
        return length[x]+1;
    }
    length[x]=0;
    for(int i=0;i<G[x].size();++i){
        int tmp=dfs(G[x][i]);
        if(tmp>length[x]){
            length[x]=tmp;
            nextm[x]=G[x][i];
        }
    }
    return length[x]+1;
}
int main(){
    int n=0;
    memset(nextm,-1,sizeof(nextm));
    memset(length,-1,sizeof(length));
    while(~scanf("%d%d",&W[n],&S[n])){
        ++n;
        for(int i=0;i<(n-1);++i){
            if(find_mat(i,n-1)){
                G[n-1].push_back(i);
            }
            if(find_mat(n-1,i)){
                G[i].push_back(n-1);
            }
        }
    }
    int res=-1,ans=0;
    for(int i=0;i<n;++i){
        if(dfs(i)>ans){
            ans=length[i]+1;
            res=i;
        }
    }
    printf("%d\n%d\n",ans,res+1);
    while(nextm[res]!=-1){
        printf("%d\n",nextm[res]+1);
        res=nextm[res];
    }
    return 0;
}