B的三种做法

B-小红的伪回文子串（easy）

定义一个字符串的“伪回文值”是：修改最少字符数量使得其变成回文串的修改次数。例如，"abca"的伪回文值是1。任何回文串的伪回文值是0。

给定一个字符串，求出所有连续子串的伪回文值之和。(长度不超过100)

枚举|区间dp

法一：枚举所有字串，用双指针从两边判断需要修改多少个字符才能变为回文串。

​

法二：：表示字串的伪回文值

​ 若

​ 否则，

​ 枚举所有字串，求和得答案。

​

法三：计算每一对字符对答案的贡献。

​ (从0开始)位置为是多少个子串的对称位置呢？个。

​ 如果，则该对字符对答案的贡献为.

​ 枚举所有字符对，求和贡献。

​

import java.io.*;
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws Exception {
        char[] s = sc.next().toCharArray();
        int n = s.length;
        long ans = 0;
        for(int i = 0; i < n - 1; i ++){
            for(int j = i + 1; j < n; j ++){
                for(int l = i, r = j; l < r; l ++, r --){
                    if(s[l] != s[r]) ans ++;
                }
            }
        }
        pw.println(ans);
        pw.flush();pw.close(); 
    }
}
--------------------------------------------------------------------------------------
import java.io.*;
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws Exception {
        char[] s = sc.next().toCharArray();
        int n = s.length;
        int dp[][] = new int[n + 1][n + 1];
        long ans = 0;
        for(int j = 2; j <= n ; j ++){
            for(int i = 1; i <= j - 1; i ++){// left:i right:j
                if(s[j - 1] == s[i - 1])  dp[i][j] = dp[i + 1][j - 1];
                else dp[i][j] = dp[i + 1][j - 1] + 1;
                ans += dp[i][j];
            }
        }
        pw.println(ans);
        pw.flush();pw.close(); 
    }
}
------------------------------------------------------------------------------
import java.io.*;
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws Exception {
        char[] c = sc.next().toCharArray();
        int n = c.length;
        long ans = 0;
        for(int i = 0; i < n - 1; i ++){
            for(int j = i + 1; j < n; j ++){
                if(c[i] != c[j]) ans += Math.min(i + 1, n - j);
            }
        }
        pw.println(ans);
        pw.flush();pw.close(); 
    }
}