题解：AT_abc225_f [ABC225F] String Cards

· · 题解

第一眼：建议降红。

风风火火地交上去后发现并没有那么简单。

其实这道题很快就能看出来一个看起来正确的写法:

bool cmp(string a,string b){
    return a + b < b + a;
}

然后就 WA 了。。。。。。

其实这道题的正解其实是动态规划。

我们定义 f_{i,j} 为从 S_i 到 S_n 中选取 j 个字符串，得到的字典序最小的结果。

状态转移就会有选和不选两种情况。

题目要求我们求字典序最小的结果，所以最终的状态转移方程为：

f_{i,j} = \min(f_{i-1,j},f_{i-1,j-1} + S_i)

最终输出 f_{1,k}。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n,k;
string s[55],f[55][55];
bool cmp(string A,string B){return A+B<B+A;}
int main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; i++)cin>>s[i];
    sort(s+1,s+n+1,cmp);//先排序 
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= k; j++)
            f[i][j] = char('z'+1);  //初始化数组 f
    for(int i = n; i >= 1; i--)
    {
        if(n == i) //特判
        {
            f[i][1] = s[i];
            continue;
        }
        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;//华丽收场
}