NOIP2023 国庆集训 A 组 Day6
A. 机型超算（boolean）
直接输出"V”,40pts;
正解：栈
B. 字符修改（master）
裸爆力，50pts;
正解：
| 暴力枚举两个后缀，计算最长能匹配多少前缀。最优策略一定是贪心改掉前k个失配的字符，这样我们一定能够考虑到所有可能最优的解; 时间复杂度：o(n^3)。 |
#include
using namespace std;
int n,k;
string s,t;
int ans;
int main() {
freopen("master.in", "r", stdin);
freopen("master.out", "w", stdout);
cin>>n>>k;
cin>>s>>t;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
int si=i,ti=j,l=0;
for(; si<n && tik)
break;
}
ans=max(ans,si-i);
}
cout<<ans;
return 0;
}
D. 公共子串（lcs）
求出lcs,40pts;
正解：由f[i][j]—>g[i][j]。
#include
using namespace std;
string s,t;
int n,m;
int dp[5003][5003];
bool f1,f2;
int main() {
freopen("lcs.in", "r", stdin);
freopen("lcs.out", "w", stdout);
cin>>s>>t;
n=s.size()-1;
m=t.size()-1;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(s[i-1]==t[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
cout<<dp[n][m]<<endl<<7;
return 0;
}