HDU1160FatMouse'sSpeed简单DP

 1 #include
 2 #include
 3 #include
 4 #include
 5 
 6 using namespace std;
 7 
 8 const int maxn=1005;
 9 
10 int dp[maxn];                    //以第i个为结束元素的序列的最大值
11 int pre[maxn];                   //记录序列
12 
13 struct Node
14 {
15     int w,s,num;                 //num记录输入的顺序
16 }node[maxn];
17 
18 bool cmp(Node a,Node b)
19 {
20     if(a.w==b.w)
21         return a.s>b.s;
22     return a.w<b.w;
23 }
24 
25 //输出路径
26 void output(int cur)
27 {
28     if(pre[cur]!=-1)
29         output(pre[cur]);
30     cout<endl;
31 }
32 
33 int main()
34 {
35     //freopen("in.txt","r",stdin);          //记住要注释掉
36 
37     int u,v;
38     int tot=1;
39 
40     while(cin>>u>>v)
41     {
42         node[tot].w=u;
43         node[tot].s=v;
44         node[tot].num=tot++;
45     }
46 
47     sort(node+1,node+tot,cmp);
48 
49     memset(pre,-1,sizeof(pre));
50 
51     for(int i=1;i)
52         dp[i]=1;
53 
54     for(int i=1;i)
55     {
56         for(int j=1;j)
57             if(node[j].wnode[i].s)
58                 if(dp[j]+1>dp[i])
59                 {
60                     dp[i]=dp[j]+1;
61                     pre[i]=j;
62                 }
63     }
64 
65     int ans=0;
66     int cur;
67     for(int i=1;i)
68         if(dp[i]>ans)
69         {
70             ans=dp[i];
71             cur=i;
72         }
73 
74     cout<endl;
75 
76     output(cur);
77 
78     return 0;
79 }