P9232 [蓝桥杯 2023 省 A] 更小的数（区间DP）

求大数字某连续部分反转后，比原数字小的个数

思路：自前向后遍历

ai是位于数字第i位的数字

aj是位于数字第j位的数字（i<=j）

ai>aj             f[ai][aj]=1;

ai<aj             f[ai][aj]=0;

ai==aj           f[ai][aj]=f[ai+1][aj-1]

(由于是连续部分反转，若该部分下一层中

有反转后变小的部分，反转后整体也会变小)

        

	cin >> arr;int len = strlen(arr);for (int i = len - 1; i >= 0; i--){for (int j = i+1; j < len; j++){if (arr[i] > arr[j])f[i][j] = 1;else if (arr[i] < arr[j])f[i][j] = 0;elsef[i][j] = f[i + 1][j - 1];if (f[i][j] == 1)s++;}}