问题简述 给出一个长度为N (1 ≤ N ≤ 30,000)的整数数组D[]，其中1 ≤ D[i]≤ 3 。 要求通过该动元素的值的方式（但是不能改出1，2，3之外），使得数组有序（不升序或者不降序都行）。 问最少需要改动多少个元素。 分析 这是POJ3671[1]的强化版本，同样可以划归为LIS问题[2]问题，用O(nlogn)的算法求解。 但是和POJ3671[1]一样，实际上这个问题也是存在O(n)的算法的。 具体思路和POJ3671的O(n)解法[1]大同小异。 先只考虑排成不降序的情况，观察最后形成的有序数组，由于元素只能是1,2,3，所以它必然是如下形式： 11111….122222….23

问题简述 给出一个长度为N (1 ≤ N ≤ 30,000)的由1和2组成的序列，通过修改1为2，修改2为1的方式，使序列变成不降序，问最少改动次数是多少。 分析 经典的做法是化归为LIS问题[1]，但实际上这个问题有O(n)的算法。 我们考虑最后得到的不降序列，由于元素只能为1和2，所以它一定是如下形式的： 111…12222…..2 其中有i个1和N-i个2。 改动的次数等于原序列前i个元素中2的个数f[i]，加上后N-i个元素中1的个数g[i]。 所以我们可以通过穷举i来寻找最小值，即我们的解为min{f[i]+g[i],0<=i<=N}。 如果能够快速计算f[i]和g[i]，那么算

问题简述 已知一个n元高次方程： 其中：x1, x2,…,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。 假设未知数1 <= xi <= M, i=1,,,n，求这个方程的整数解的个数。 1 <= n <= 6；1 <= M <= 150。 方程的整数解的个数小于231。 ★本题中，指数Pi(i=1,2,…,n)均为正整数。 分析 将方程移项，左右各一半。以n=6为例,形成f(x1,x2,x3)=g(x4,x5,x6)的形式。 然后搜索左边（枚举前三个未知数的所有值），每搜索一组x1,x2,x3，则将对应的f(x1,x2,x3)放入一个具有查找功