HDU - 1160 FatMouse‘s Speed

2024-04-27 12:18

文章标签 hdu speed 1160 fatmouse

本文主要是介绍HDU - 1160 FatMouse‘s Speed，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<utility>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
using namespace std;typedef long long LL;           //数据太大了记得用LL,还有把INF也得换
typedef pair<int, int> P;const int maxn = 1e7+10;        //cf数组最多差不多是这么多，1e8就会段错误
const int V_MAX = 800 + 10;
const int mod = 10007;
const int INF = 0x3f3f3f3f;     //如果数据范围为long long，记得把INF的值换了
const double eps = 1e-6;        //eps开太小二分容易死循环,所以直接来个100次循环就好了//多组输入时,maxn太大,用memset()会超时,血的教训;
struct Mouse { int W, S, no;Mouse() {}Mouse(int WW, int SS, int NN) : W(WW), S(SS), no(NN) {}bool operator < (const Mouse &b) {if(W != b.W) return W < b.W;else return S > b.S;}
};//最长单调递增子序列;vector<Mouse> m;
int dp[2000], pre[2000];void output(int index) {if(index == 0) return;output(pre[index]);cout << index << endl; 
}void solve() {int n = m.size();sort(m.begin(), m.end());for(int i = 0; i < n; i++) {dp[i] = 1;for(int j = 0; j < i; j++) {if(m[i].W > m[j].W && m[i].S < m[j].S && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;pre[m[i].no] = m[j].no;}}}int mx = 0, ff;for(int i = 0; i < n; i++) {if(mx < dp[i]) {mx = dp[i];ff = m[i].no;}}cout << mx << endl;output(ff);
}int main()
{ios::sync_with_stdio(false);           //关了流同步就别用c的输入//freopen("D:\\in.txt", "r", stdin);int cnt = 0, w, s;while(cin >> w >> s) m.emplace_back(Mouse(w, s, ++cnt));solve();return 0;
}