Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51645 _ 最优子序列 C++ 运行超时 20 1000 MS 8648 KB 782 2022-07-13 12:22:27

Tests(4/20):


#include <bits/stdc++.h> using namespace std; const int MXN = 3005; const int MXK = 12; int N, K, Tp; char str[MXN]; int cnt[MXN][MXK], dp[MXN][1 << MXK]; int main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); cin >> N >> K >> Tp >> (str + 1); for (int i(1); i <= N; ++i) { for (int j(0); j != K; ++j) cnt[i][j] = cnt[i - 1][j]; ++cnt[i][str[i] - 'a']; for (int j(0); j != (1 << K); ++j) { for (int k(0); k != K; ++k) { if (!(j & (1 << k))) continue; for (int l(0); l != i; ++l) { int t(dp[l][j ^ (1 << k)] + cnt[i][k] - cnt[l][k]); dp[i][j] = max(dp[i][j], t); } } } } int ans(0); for (int j(0); j != (1 << K); ++j) ans = max(ans, dp[N][j]); cout << ans << endl; return 0; }


测评信息: