字母交换

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;

string str;
int m;

int cnt(const vector<int>& vec) {
    int n = vec.size();
    vector< vector<int> > dp(n, vector<int>(n, 0));
    for(int i=0; i<n-1; ++i) {
        dp[i][i+1] = abs(vec[i+1] - vec[i]) - 1;
    }
    for(int j=2; j<n; ++j) {
        for(int i=0; i<n-j; ++i) {
            int row = i, col = i+j;
            dp[row][col] = dp[row+1][col-1] + abs(vec[col] - vec[row]) - (col-row);
        }
    }
    int Max = 0;
    for(int i=0; i<n; ++i) {
        for(int j=i; j<n; ++j) {
            if (dp[i][j] <= m) {
                Max = max(Max, j-i+1);
            }
        }
    }
    return  Max;
}


int main()
{
    cin >> str >> m;
    vector< vector<int> > vec(26);
    for(int i=0; i<str.size(); ++i) {
        vec[str[i]-'a'].push_back(i);
    }
    int Max = 0;
    for(int k=0; k<26; ++k) {
        Max = max(Max, cnt(vec[k]));
    }
    cout << Max << endl;
    return 0;
}
/*
lufhkcyqnnheshcogbovclcxrfneppkxdvolqtstdkmgsscvfvnnigltgyardkfvavrrwbblzcxzwmteonksiaswfvfsgpxwosev 200
hkdbqojqvxlfulshrhpysezhlyzolb 20
ooxnwetkuvpqjuabmovhkpypxbgpxzemuupqvavonyfscmkrvsvixcejdrutwwfndzkdxbrwgptievanpqfzlprwyqupidspcgrw 200
*/

	

动态规划状态转移方程dp[i][j] = dp[i+1][j-1] + abs(vec[j] - vec[i]) - (j-i);
dp[i][j]第i个数到第j个数移动的次数

def cal(p,m):
    dp = [[0 for i in range(len(p))] for j in range(len(p))]
    for i in range(0,len(p)-1):
        dp[i][i+1] = p[i+1]-p[i]-1
    for le in range(2,len(p)):
        for i in range(0,len(p)-le):
            j = i+le
            dp[i][j] = dp[i+1][j-1]+(p[j]-p[i])-(j-i)
    res = 0
    for i in range(len(p)):
        for j in range(i,len(p)):
            if dp[i][j]<=m:
                res = max(res,j-i+1)
    return res

inp = input().split()
s,m = inp[0],int(inp[1])
positions = [[] for i in range(26)]
for i in range(len(s)):
    positions[ord(s[i])-ord('a')].append(i)
res = 0
for i in range(26):
    res = max(res,cal(positions[i],m))
print(res)

while True:
    try:
        line = input().split()
        s = list(line[0])
        n = int(line[1])
        # 将字符去重复
        ss = set(s)
        maxsub = 1
        for i in ss:
            # 记录字符出现的位置
            pos = []
            for j in range(len(s)):
                if s[j] == i:
                    pos.append(j)
            ll = len(pos)
            if ll < maxsub:
                continue
            temp = 1
            dp = [[1 for _ in range(ll)] for _ in range(ll)]
            for lens in range(2,ll+1):
                for j in range(ll+1-lens):
                    k = j + lens - 1
                    dp[j][k] = dp[j+1][k-1] + pos[k] - pos[j] + 1 - lens
                    if dp[j][k] <= n:
                        temp = lens
            maxsub = max(maxsub, temp)
        print(maxsub)
    except:
        break

#include <bits/stdc++.h>
using namespace std;

bool F(vector<vector<int>> &v, int n, int m){
    bool flag = false;
    for(int i=0;i<v.size();i++){
        if(v[i].size() < n)
            continue;
        for(int j=0;j<v[i].size();j++){
            if(j+n > v[i].size())
                break;
            int s = 0, t = j+n/2;
            for(int k=j;k<j+n;k++){
                if(k<=t)
                    s += (v[i][t] - (t-k) - v[i][k]);
                else
                    s += (v[i][k] - v[i][t] - (k-t));
            }
            if(s <= m)
                flag = true;
        }
    }
    return flag;
}

int main(){
    string s;
    int m, cnt=0;
    cin>>s;
    scanf("%d", &m);
    map<char, int> mp;
    for(auto &c: s)
        mp[c] = cnt++;
    vector<vector<int>> v;
    for(int i=0;i<cnt;i++){
        vector<int> t;
        v.push_back(t);
    }
    for(int i=0;i<s.size();i++)
        v[mp[s[i]]].push_back(i);
    int l=0, r=s.size()+1;
    while(l<r){
        int k = (l+r)>>1;
        if(F(v, k, m))
            l = k+1;
        else
            r = k;
    }
    if(l==0)
        puts("0");
    else
        printf("%d\n", l-1);
    return 0;
}

"""
# 动态规划题。
# 首先题目说只有小写字母，字符的类型的只有26种，为了简化问题我们只要讨论a字符,其他字符只要重复这个过程即可
# 对于a字符，只需要记下他的位置char[c],就是把这些位置转换成连续的最少转换次数，这就可以dp了。
# 设dp[i][j]表示把i到j这一段合在一起最少需要的次数，根据不等式|x−a|+|x−b|a), 可以推导出其状态转移方程为:
# dp[i][j]=dp[i+1][j−1]+char[j]−char[i]−(leng-1）
# 枚举的时候是先枚举小区间然后再枚举大区间。
"""
def exchange(char,m):
    n = len(char)
    ans = 0
    dp = [[0]*n for i in range(n)]
    for i in range(n-1):
        dp[i][i+1] = char[i+1] - char[i] - 1 # 相邻两个的交换的最小次数
        if dp[i][i+1] < m:
            ans = 2
    for leng in range(2,n):
        for i in range(0,n-leng):
            j = leng + i
            dp[i][j] = dp[i+1][j-1] + (char[j]-char[i]) - (j-i-1)
            if dp[i][j] < m:
                ans = leng + 1
    return ans
s, m = input().split()
m = int(m)
char = [[] for _ in range(26)] # 记录字符串中每一字母的位置
for i in range(len(s)):
    char[ord(s[i])-97].append(i)
res = 0
for i in range(26):
    if char[i]:
        res = max(res,exchange(char[i],m))
print(res)

这一题我觉得作为笔试题，还是有些难度的。
思路是这样的，我们对每一个字母分别求可能连接的成的最大距离。
这时候就需要用26个列表，来分别保存每个字母的出现在原字符串中的位置（代码中v表示）。
我们下面针对一个字母考虑：
dp[i][j]:表示v中第i到第j个位置的字母如果需要移动到在一起，需要移动的次数。
那么转移方程就有了

dp[left][right] = dp[left+1][right-1] + (v[right] - v[left] - 1) - (right - left - 1)

这里做一下说明：
对于最左边位置left和最右边位置right字符串，如果只需要将这俩字符移动在一起，则需要固定的(v[right] - v[left] - 1)次移动，但是这个区间内已经有了移动好的(right - left - 1)个字母，所以可以少移动这么多次，固需要减去这个数字。

s, m = input().split()
m = int(m)

from collections import defaultdict

d = defaultdict(list)

for i,c in enumerate(s):
    d[c].append(i)

res = 0
for k,v in d.items():
    n = len(v)
    dp = [[0] * n for _ in range(n)]
    for i in range(1,n):
        dp[i-1][i] = v[i]-v[i-1]-1
    for k in range(2,n):
        for i in range(n-k):
            left, right = i, k+i
            dp[left][right] = dp[left+1][right-1] + (v[right] - v[left] - 1) - (right - left - 1)

for i in range(n):
    for j in range(i,n):
        if dp[i][j] <= m:
            res = max(res, j-i+1)

print(res)

import java.util.*;

public class Main{
    static int res = 1;
    public static void main(String[] args){
        
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String str = input.split(" ")[0];
        int m = Integer.parseInt(input.split(" ")[1]);
        
        HashMap<Character, List<Integer>> map = new HashMap<>();
        char[] chars = str.toCharArray();
        int len = chars.length;
        
        for(int i = 0; i < len; i++){
            List<Integer> list = map.getOrDefault(chars[i], new ArrayList<>());
            list.add(i);
            map.put(chars[i], list);
        }
        
        for(int i = 0; i < len; i++){
            char c = chars[i];
            List<Integer> list = map.get(c);
            moveTogether(list, i, m);
            /*
            int lessCount = 0;
            for(int num : list){
                if(num < i){
                    lessCount++;
                }
                else{
                    break;
                }
            }
            int greatCount = list.size()-1-lessCount;
            for(int j = 0; j < lessCount; i++){
                int cur = list.get(j);

                // 现在这个节点的位置在cur,要移动到          （0 1 j 3 4 ... lessCount-1）i
                // lesscount-2的时候对应i-2
                // lesscount-1的时候对应i-1
                int target = i + j - lessCount;
                int times = 
            }
        }
*/
        
        
        
    }
                System.out.println(res);
        
  
    
        
    }
            // 在times步内，尽可能把list里面的数字移动到mid周围
        public static void moveTogether(List<Integer> list, int mid, int times){
            int len = list.size();
            int mid_index = 0;
            for(int i = 0; i < len; i++){
                if(list.get(i) == mid){
                    mid_index = i;
                    break;
                }
            }
            int left_index = mid_index-1;
            int right_index = mid_index+1;
            int count = 1;
            // mid为中心的左右边界
            int left_mid = mid-1;
            int right_mid = mid+1;
            while(times > 0){
                if(left_index < 0 && right_index >= len){
                    break;
                }
                
                // 看一下左边和右边哪个更近一点
                int left_dist;
                if(left_index < 0)    
                    left_dist = Integer.MAX_VALUE / 2;
                else    
                    left_dist = left_mid - list.get(left_index);
                int right_dist;
                if(right_index >= len)   {
                    right_dist = Integer.MAX_VALUE / 2;
                } 
                else {
                    right_dist = list.get(right_index) - right_mid; 
                }    
                   
                if(left_dist > right_dist){
                    // 右边靠更加近一点
                    if(times < right_dist)    break;
                    times -= right_dist;
                    right_mid++;
                    count++;
                    right_index++;
                }
                else{
                    if(times < left_dist)    break;
                    times -= left_dist;
                    left_mid--;
                    left_index--;
                    count++;
                }
            }
            res = Math.max(count, res);
        }
  
}

using System;
using System.Collections.Generic;

namespace CSExercise
{
    class Program
    {
        static int maxTurn;
        static Dictionary<char, List<int>> dict;
        
        static int MaxLength(List<int> list)
        {
            if (list.Count == 0) return 0;

            List<int> sortedList = new List<int>();

            int centerIndex = list.Count / 2;
            int moveToIndex = list[centerIndex];
            
            for (int i = 0; i < list.Count; i++)
            {
                list[i] = Math.Abs(moveToIndex - list[i]) - Math.Abs(centerIndex - i);
            }

            list.Sort();
            int result = 0;
            int turn = maxTurn;
            foreach (int item in list)
            {
                if (item > turn)
                {
                    break;
                }
                result++;
                turn -= item;
            }
            return result;
        }
        
        static void Main(string[] args)
        {
            dict = new Dictionary<char, List<int>>();
            string[] str = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);
            string original = str[0];
            maxTurn = int.Parse(str[1]);
            for (int i = 0; i < original.Length; i++)
            {
                if (dict.TryGetValue(original[i], out List<int> list))
                {
                    list.Add(i);
                }
                else
                {
                    List<int> l = new List<int>();
                    l.Add(i);
                    dict.Add(original[i], l);
                }
            }

            int maxLength = 0;
            foreach (var item in dict)
            {
                maxLength = Math.Max(maxLength, MaxLength(item.Value));
            }
            Console.WriteLine(maxLength);
        }
    }
}

import java.util.*;
public class Main
{
    private static int m;
    private static int res=0;
    private static Map<Character,ArrayList<Integer>> mymap=new TreeMap<>();
    public static void main(String []args)
    {
        Scanner cin=new Scanner(System.in);
        String s=cin.next();
        m=cin.nextInt();
        for(int i=0;i<s.length();i++)
        {
            char c=s.charAt(i);
            if(mymap.containsKey(c))
            {
                ArrayList<Integer> list=mymap.get(c);
                list.add(i);
                mymap.put(c,list);
            }
            else
            {
                ArrayList<Integer> list=new ArrayList<Integer>();
                list.add(i);
                mymap.put(c,list);
            }
        }
        execute();
        System.out.print(res);
    }
     public static void execute()
     {
          for(char c:mymap.keySet())
          {
              ArrayList<Integer> list=mymap.get(c);
              int n=list.size();
              int [][]dp=new int[n][n];
              for(int l=2;l<=n;l++)
                  for(int left=0;left+l<=n;left++)
                  {
                      dp[left][left+l-1]=dp[left+1][left+l-2]+list.get(left+l-1)-list.get(left)-1-(l-2);
                      if(dp[left][left+l-1]<=m)
                      {
                          res=Math.max(res,l);
                      }
                  }
          }
     }
}