好久不写题了，写个试试。这个算Mathematica里吧，要不东西太少了。题目：http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1185大概是说，给你一个数组，求这个数组的逆序数。求逆序数的暴力方法：对于输入a[i]求a[1]…a[i-1]中大于于a[i]的数的个数,然后对所有这样的数求和。因而是o(n^2)。正常解法：首先想到排序，之后自然想到归并排序。考虑到归并排序中要对两个排列好的子串依次送入结果串，并且可以根据目前子串位置决定后面子串在前面子串的排名，因此可以得到逆序数。对于任意两个子串，后面子串中的数的位置不影响其对于前面子串的逆序数。而任意一个数的逆序数由在本子串的逆序数与对于前子串的逆序数的和。因此可以将两个子串排序，根据后面子串中数在前面子串中的插入位置决定其在前面子串的逆序数。对于本子串的逆序数由递归求得。代码：点击获取源文件

题目：http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1004 这题是说，给一个数列，问最少去掉多少个元素可以使这个数列成为前一半严格递增后一半严格递减的数列（前后两半共用中间最大的元素）。比如1,2,3,4,3,4，2,1，去掉第二个4之后得到1,2,3,4,3,2,1。 解法：最长单调子序列。 最长单调子序列求解用到DP，因为最长单调子序列具有最有子结构，例如考虑最优子序列l,如果l由l1、l2两个序列构成，则l1、l2都是原序列以l1最后一个元素为最后元素的序列的最长单调子序列。证明：如果l1或l2不是最优的，则找到最优的l3替换l1或l2，则新形成的序列比原l序列更长，因此l不是最优解，矛盾，因此l1、l2必须是最优解。根据这一性质，从前向后找最优子结构。dp(i)=max(dp(j)),j为0到i-1的，满足in(j)<in(i)的所有整数。 具体到这题首先正反两次求最长单调子结构，然后按照每一位找y=max(dp1(i)+dp2(i))则解为n-(y-1)。 代码: 点击这里下载