当前位置: 代码迷 >> 综合 >> HDU 1160 FatMouse's Speed .
  详细解决方案

HDU 1160 FatMouse's Speed .

热度:125   发布时间:2023-09-23 06:32:17.0

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1160

先对体重升序排序,然后求s的最长下降子序列

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=10000+5;
struct Mice
{int w,s,idx;bool operator < (const Mice& m) const {return w<m.w;}
}mice[maxn];
int d[maxn],p[maxn];
int main()
{int w,s,n=1;while(scanf("%d%d",&w,&s)!=EOF)mice[n++]=Mice{w,s,n-1};sort(mice+1,mice+n);int MaxP,Max;for(int i=1;i<n;i++){d[i]=1;for(int j=1;j<i;j++){if(mice[i].w>mice[j].w&&mice[i].s<mice[j].s){if(d[i]<d[j]+1){d[i]=d[j]+1;p[i]=j;}}}if(Max<d[i]){Max=d[i];MaxP=i;}}cout<<Max<<endl;vector<int> ans; ans.reserve(maxn);for(int i=MaxP;i!=0;i=p[i])ans.push_back(mice[i].idx);for(int i=ans.size()-1;i>=0;i--)cout<<ans[i]<<endl;return 0;
}