- 导弹拦截
- 2018-03-19 21:01:54 @
lol
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int missile[25], n, f[25], pre[25], tmp, cnt, last;
bool flag, vis[25];
inline int read(){
if (flag) return 0;
char ch = getchar();
int x = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9'){x *= 10; x += ch - '0'; ch = getchar();}
if (ch == '\n') flag = true;
return x;
}
inline void process(){
for (int i = last; i != 0; i = pre[i]) {
vis[i] = true;
}
}
inline int lds(){
memset(pre, 0, sizeof pre);
for (int i = 1; i <= n; i++) f[i] = 1;
for (int i = 1; i <= n; i++){
for (int j = i - 1; j >= 1; j--){
if (missile[i] <= missile[j] && !vis[j] && !vis[i]) {
if (f[j] + 1 > f[i]) {f[i] = f[j] + 1; pre[i] = j; last = i;}
}
}
}
return f[last];
}
int main(){
while (missile[++n] = read()); n--;
cout << (tmp = lds());
tmp = n - tmp;
while (tmp != 0){
// cout << tmp << endl;
process();
tmp -= lds();
cnt++;
}
cout << "," << cnt << endl;
//for (int i = 1; i <= n; i++) cout << f[i] << endl;
return 0;
}
1 条评论
-
JimmyChen LV 8 @ 2018-03-19 21:12:02
问题一大坨.......好久没碰LCS了口意
- 1