目录

题目 

思路

代码

---

题目 

思路

        题目说求数组某个区间中的数进行翻转，由于区间选择多，首先想到DP问题。

        第一版想到的方法（错误的），当进行状态计算的时候，无法判定区间是否翻转后满足要求，即反转后的值小于翻转前的值。

        其二有个错误的点，对于包含 ， 的区间  进行翻转，只能被认定作为一个方案，无法从 和  中传递过来，意思就是  区间中的区间进行翻转是与  无关的。

        看了别人的讲解后，恍然大悟。

        是一个区间动态规划问题，我们先枚举每个小区间，然后向大区间递增，大区间是否可以翻转满足要求，1.看是否右端点<左端点，2.如果右端点=左端点，看它比它小的一个区间是否可以翻转，可以，那么这个区间就可以。

        总结为：

• 
• 
• 其余情况不做处理

正确的DP分析： 

代码

import java.io.*;class Main{static int N = 5010;static int n;static long res;static int[] a = new int[N];static int[][] f = new int[N][N];public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));String s = in.readLine();n = s.length();for(int i=1;i<=n;i++) a[i] = Integer.parseInt(String.valueOf(s.charAt(i-1)));// 区间合并一般都先将小区间进行计算for(int len = 2;len<=n;len++){ // 枚举长度for(int i=1;i<=n;i++){ // 枚举左端点int j = i+len-1; // 右端点if(j>n) continue; // j<nif(a[j]<a[i]) f[i][j] = 1; //如果右端点小于左端点if(a[i]==a[j]&&f[i+1][j-1]==1) f[i][j] = 1; // 或者右端点等于左端点，但是左端点+1的数 > 右端点-1的数if(f[i][j]==1) res++; // 如果可以，res++}}System.out.println(res);}
}