这题是真的强。。
我们肯定是先按照 \(a + b < b + a\) 排序,然后 dp。
设 \(f_{i, j}\) 为后 \(i\) 个串,选 \(j\) 个拼接而成的字典序最小的串。
不从前往后是因为,前面的字典序最小不一定能使后面的小(比如 baa b
和 ba b
)。
然后就直接转移就好了。
code
// Problem: F - String Cards
// Contest: AtCoder - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)
// URL: https://atcoder.jp/contests/abc225/tasks/abc225_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 55;
int n, m;
string a[maxn], f[maxn][maxn];
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1, [&](string a, string b) {
return a + b < b + a;
});
for (int i = 0; i <= m; ++i) {
f[n][i] = "{";
}
f[n][0] = "";
f[n][1] = a[n];
for (int i = n - 1; i; --i) {
for (int j = 0; j <= m; ++j) {
f[i][j] = f[i + 1][j];
if (j) {
f[i][j] = min(f[i][j], a[i] + f[i + 1][j - 1]);
}
}
}
cout << f[1][m];
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest String Cardsbeginner atcoder contest cards beginner atcoder contest string contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334