从前往后做,不过添加了一维长度总和的状态,WA了,求hack
查看原帖
从前往后做,不过添加了一维长度总和的状态,WA了,求hack
736787
hhhqx楼主2024/7/30 11:37

AT官方题解里的所有hack都过了,但还是WA了,求hack数据?

提交记录:https://atcoder.jp/contests/abc225/submissions/56126262

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int n, k;
string s[53], dp[53][53][103];
bool vis[53][53][103];

int main(){
  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> s[i];
  }
  sort(s + 1, s + 1 + n, [](string i, string j){ return i + j < j + i; });
  vis[0][0][0] = 1;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j <= i; j++){
      for(int l = 0; l <= 50; l++) vis[i][j][l] = vis[i-1][j][l], dp[i][j][l] = dp[i - 1][j][l];
    }
    for(int j = 0; j <= i; j++){
      for(int l = 0; l <= 50; l++){
        if(!vis[i - 1][j][l]) continue;
        vis[i][j + 1][l + s[i].size()] = 1;
        if(dp[i][j + 1][l+s[i].size()].empty()){
          dp[i][j + 1][l+s[i].size()] = dp[i - 1][j][l] + s[i];
        }else dp[i][j + 1][l+s[i].size()] = min(dp[i][j + 1][l+s[i].size()], dp[i - 1][j][l] + s[i]);
      }
    }
  }
  string ans;
  for(int l = 0; l <= 50; l++){
    if(vis[n][k][l] && !dp[n][k][l].empty()){
      ans = (ans.empty() ? dp[n][k][l] : min(ans, dp[n][k][l]));
    }
  }
  cout << ans;
  return 0;
}
2024/7/30 11:37
加载中...