NC24607. [USACO 2011 Ope S]Forgotten Password
描述
输入描述
* Line 1: Two space-separated integers: L and NW
* Line 2: A string of length L: P
* Lines 3..NW+2: Line i+2 contains the ith word in the dictionary:
输出描述
* Line 1: The lexicographically least password that fits
示例1
输入:
15 6 a??l?ban??????? apple cow farmer banana bananas pies
输出:
applebananapies
C++14(g++5.4) 解法, 执行用时: 176ms, 内存消耗: 26548K, 提交时间: 2020-03-08 13:40:13
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 4e5+100; string s,a[maxn],dp[maxn]; bool check(int x,int y){ for (int i = x - a[y].size(), j = 0; i < x; i++, j++) if (s[i] != '?' && s[i] != a[y][j]) return 0; return 1; } int main() { ios::sync_with_stdio(0); int n,m; cin>>n>>m>>s; for(int i=1; i<=m; i++) cin>>a[i]; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { int L=a[j].size(); if (L > i || (dp[i - L] == "" && i - L != 0)) continue; if(check(i,j)){ if(dp[i]==""||dp[i-L]+a[j]<dp[i]) dp[i]=dp[i-L]+a[j]; } } } cout<<dp[n]<<endl; return 0; }
C++11(clang++ 3.9) 解法, 执行用时: 183ms, 内存消耗: 1528K, 提交时间: 2020-04-03 09:35:04
#include<bits/stdc++.h> using namespace std; char s[1005]; string f[1005],a[1005]; int n,m; bool check(int x,int y) { for(int i=0;i<a[y].size();i++) if(s[x+i+1]!='?'&&s[x+i+1]!=a[y][i]) return 0; return 1; } int main() { cin>>n>>m; scanf("%s",s+1); for(int i=1;i<=m;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int xx=i-a[j].size(); if(xx<0||xx&&f[xx].empty()) continue; if(check(xx,j)) if(f[i].empty()||f[i]>f[xx]+a[j]) f[i]=f[xx]+a[j]; } cout<<f[n]; return 0; }