英文企业网站源码 asp网站类游戏网站开发

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

思路：自前向后遍历

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++;}}