首页 > 代码库 > UVA 231 Testing the CATCHER
UVA 231 Testing the CATCHER
题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=167
这道题实际上就是在一个序列中找出最长的非降sub序列。第一个序列就是原序列,第二个是排序过的非降序列,然后找出Longest common substring,就是答案。
代码如下:
#include <iostream> #include <math.h> #include <stdio.h> #include <cstdio> #include <algorithm> #include <string.h> #include <cstring> #include <queue> #include <vector> #include <functional> #include <cmath> #define SCF(a) scanf("%d", &a) #define IN(a) cin>>a #define FOR(i, a, b) for(int i=a;i<b;i++) typedef long long Int; using namespace std; bool cmp(int a, int b) { if (a > b) return true; return false; } int main() { vector<int> missiles, ordered; int num = 0; int n; int test = 0; while (SCF(n)) { if (n == -1 && num == 0) break; else if (n == -1) { sort(ordered.begin(), ordered.begin() + num, cmp); int** match; match = new int*[num + 1]; FOR(i, 0, num + 1) match[i] = new int[num + 1]; FOR(i, 0, num + 1) { match[i][0] = 0; match[0][i] = 0; } FOR(i, 1, num + 1) { FOR(j, 1, num + 1) { if (ordered[i - 1] == missiles[j - 1]) match[i][j] = match[i - 1][j - 1] + 1; else match[i][j] = max(match[i][j - 1], match[i - 1][j]); } } if (test > 0) printf("\n"); printf("Test #%d:\n", ++test); printf(" maximum possible interceptions: %d\n", match[num][num]); while (!missiles.empty()) { missiles.pop_back(); } while (!ordered.empty()) { ordered.pop_back(); } num = 0; } else { missiles.push_back(n); ordered.push_back(n); num++; } } return 0; }
UVA 231 Testing the CATCHER
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。