B-Sequence Game_牛客IOI周赛28-普及组
题意
由于你帮助 Alice 回答得非常好，Sept 又找到了 Bob，希望能难倒他。
他给了要求 Bob 组成一个长度为 n 的新的数列 a，其中数列 a 的每一个元素 a i 都有 k 个取值。
求所有可能的数列 a 中的最长上升子序列的的最大长度。
由于 Sept 怕题目钛难，所以他答应 Bob，对于每个 i，k 个取值不降。
思路
代码
#include<bits/stdc++.h> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1e3 + 10; int a[N][5 * N], dp[N][5 * N]; bool vis[N][5 * N]; int n, k; void solve() { cin >> k >> n; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { cin >> a[i][j]; vis[i][a[i][j]] = true; } } int maxn = 0; for (int i = 1; i <= n; ++i) { maxn = 0; for (int j = 1; j <= 1000; ++j) { if (vis[i][j]) { dp[i][j] = max(dp[i][j], maxn + 1); } else dp[i][j] = dp[i - 1][j]; maxn = max(maxn, dp[i - 1][j]); } } int res = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= 1000; ++j) { res = max(res, dp[i][j]); } } cout << res << endl; } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
