专栏文章

题解：AT_abc225_f [ABC225F] String Cards

yymx2009
AT_abc225_f题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqepfix
此快照首次捕获于
2025/12/04 03:35
3 个月前
此快照最后确认于
2025/12/04 03:35
3 个月前
查看原文

前言

做这道题之前可以先去看看 P1012。

思路

想到特殊的排序方式。
当且仅当 si+sj≤sj+sis_i+s_j\le s_j+s_i 时，sis_i 排在 sjs_j 的前面。
然后就很容易陷入误区，并不是选排在最前面的就最优。 不理解就看下面这个例子：
CPP
3 2
za
z
za
排序后的顺序为 za za z，如果直接选前两个构成的字符串为 zaza 很明显不如 zaz 更优。
所以我们考虑动态规划，设 fi,jf_{i,j} 表示 [i,n][i,n] 中取 jj 个字符串形成的字典序最小的字符串。
状态转移方程为：
fi,j=min⁡(si+fi+1,j−1,fi+1,j)f_{i,j}=\min(s_i+f_{i+1,j-1},f_{i+1,j})
因为是排好序的，所以 si+fi+1,j−1s_i+f_{i+1,j-1} 肯定比 fi+1,j−1+sif_{i+1,j-1}+s_i 更优。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=60;
int n,k;
string s[N],f[N][N];
bool cmp(string x,string y){return x+y<y+x;}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>s[i];
	sort(s+1,s+1+n,cmp);
	for(int i=1;i<=n+1;i++) for(int j=1;j<=k;j++) f[i][j]='~';//'~'是一个ASCII比'z'大的字符
	f[n][1]=s[n];
	for(int i=n-1;i>=1;i--)	for(int j=1;j<=k;j++) f[i][j]=min(s[i]+f[i+1][j-1],f[i+1][j]);
	cout<<f[1][k];
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...