当前位置:网站首页>The exchange - string dp
The exchange - string dp
2022-08-02 11:00:00 【WAWA source】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define int long long
const int N = 200010;
int n,k;
string s;
vector<int>vec[30];
int f[1010][1010];
int cal(vector<int> vec)
{
int n=vec.size();
memset(f,0,sizeof f);
for(int i=0;i+1<n;i++)
f[i][i+1]=vec[i+1]-vec[i]-1;
for(int i=2;i<n;i++)
{
for(int j=0;j+i<n;j++)
{
int l=j,r=j+i;
f[l][r]=f[l+1][r-1]+abs(vec[r]-vec[l])-(r-l);
}
}
int res=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(f[i][j]<=k)res=max(j-i+1,res);
return res;
}
signed main()
{
cin>>s>>k;
for(int i=0;i<s.size();i++)
vec[s[i]-'a'].push_back(i);
int res=0;
for(int i=0;i<26;i++)res=max(res,cal(vec[i]));
cout<<res<<'\n';
}
边栏推荐
猜你喜欢
随机推荐
MSYS2 QtCreator Clangd code analysis can not find mm_malloc.h problem remedy
Oracle 19c配置ob server
10份重磅报告 — 展望中国数字经济未来
小几届的学弟问我,软件测试岗是选11k的华为还是20k的小公司,我直呼受不了,太凡尔赛了~
Oracle降低高水位
LayaBox---TypeScript---Symbols
记一次mysql查询慢的优化历程
云原生应用平台的核心模块有哪些
Three.JS程序化建模入门
智能手表前景如何?
Hub and Spoke配置案例
Camera Hal OEM模块 ---- cmr_snapshot.c
LayaBox---TypeScript---Three slash instructions
LeetCode每日一练 —— 225. 用队列实现栈
LayaBox---TypeScript---装饰器
AlphaFold又放大招,剑指整个生物界!
FinClip | 来了, 2022 年 7 月更新大盘点
Oracle查询提示 ORA-00933 SQL command not properly ended 原因排查
Geoffery Hinton: The Next Big Thing in Deep Learning
LayaBox---TypeScript---Symbols