CF10D LCIS（线性DP）

题意：\(LCIS\)输出方案
变迁の时刻，标记它

P.S:特判没\(LCIS\)的情况
//#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define ON_DEBUGG

#ifdef ON_DEBUGG

#define D_e_Line printf("-----------\n")

#define D_e(x) std::cout << (#x) << " : " <<x << "\n"

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out2.txt", "w", stdout)

#define Pause() system("pause")

#include <ctime>

#define TIME() fprintf(stderr, "\nTIME :¡¡%.3lfms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;

#define D_e(x) ;

#define FileOpen() ;

#define FilSave ;

#define Pause() ;

#define TIME() ;

#endif

struct ios {

	template<typename ATP> ios& operator >> (ATP &x) {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

		x *= f;

		return *this;

	}

}io;

using namespace std;

template<typename ATP> inline ATP Min(ATP a, ATP b) {

	return a < b ? a : b;

}

template<typename ATP> inline ATP Max(ATP a, ATP b) {

	return a > b ? a : b;

}

template<typename ATP> inline ATP Abs(ATP a) {

	return a < 0 ? -a : a;

}

const int N = 507;

#define int long long

int a[N], b[N], f[N][N];

int n, m;

pair<int, int> from[N][N];

inline void DFS(int x, int y) {

	if(!x) return;

	DFS(from[x][y].first, from[x][y].second);

	if(from[x][y].second != y) printf("%lld ", b[y]);

}

#undef int

int main() {

#define int long long

//FileOpen();

//freopen("okarin.in", "r", stdin);

//freopen("okarin.out", "w", stdout);

    io >> n;

    R(i,1,n) io >> a[i];

	io >> m;

	R(i,1,m) io >> b[i];

    R(i,1,n){

        int val=0;

        pair<int,int> p = make_pair(0, 0);

        R(j,1,m){

            if(a[i] == b[j]){

            	f[i][j] = val + 1;

				from[i][j] = p;

			}

            else{

            	f[i][j] = f[i - 1][j];

				from[i][j] = from[i - 1][j];

			}

            if(b[j] < a[i])

                if(val < f[i-1][j]){

                	p = make_pair(i - 1, j);

                	val = f[i - 1][j];

                }

        }

    }

    int now = 1;

    R(i,2,m){

    	if(f[n][i] > f[n][now]){

    		now = i;

		}

	}

    printf("%lld\n", f[n][now]);

    if(f[n][now]) DFS(n,now);

    return 0;

}
巴特西

CF10D LCIS（线性DP）

最新文章

热门文章
