错误示范

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 条评论

  • @ 2018-03-19 21:12:02

    问题一大坨.......好久没碰LCS了口意

  • 1

信息

ID
1303
难度
6
分类
动态规划 | 单调性DP 点击显示
标签
递交数
7583
已通过
2014
通过率
27%
被复制
11
上传者