本文解析四道算法竞赛题目，包括最小化酸苦度差值、动态规划解决奇数选取策略、列删除优化及区间覆盖问题。
题目：
https://jzoj.net/senior/#contest/home/1740
T1：有n种原料，有两种属性，酸性和苦性，然后，当选择n种原料时，总酸度为n种原料之积；总苦度为n种原料之和。你需要求出如何选择材料使得总酸度和总苦度的绝对值最小。
由于n非常小——1<=n<=10，所以可以直接爆搜。妥妥ac。
T2：有n个连成环的圆圈，先手可以在n个数当中先选一个数，而后手只能选上一个玩家刚刚选的数的左右两个数。最后取得数为奇数多的人获胜。问，先手可以如何选择第一个数使得最后能获胜，这样的数有多少个。
如果这道题用贪心的话，也许可以水到几十分，但是正解很明显是动态规划。usaco上有一道A Game的题目，这道题明显就是根据那道题拓展出来的。他在原题上改动了一下，把n个数变成了一个圆环。
如图：
现在，第一个人会选择这8个数当中的一个数。而后，我们发现，其实后者往两边选的时候，
我们就可以把这种抽象的“环”变成一个形象的行。简单的说，也就是把这个还剩下N-1个数的环变成4 10 5 2 9 8 1类似的一行。然后就可以从两头往中间选，这样选了之后取得的最多奇数个数，就是后手在先手取完第一个之后能在这个环里取得的最多奇数个数了。
然后我们再用整个环里的奇数个数减去后手取得的最多奇数个数，也就等于第一个人取的最优值。
现在，需要先了解一下，如何从一个数组的两头往中间选取一个最优值。
设f[i,j]表示i~j这个区间里，先手的人能取得的最优值。
那么显然
f[i,j]:=sum[i,j]-min(f[i,j-1],f[i+1,j])。
sum[i,j]表示i~j区间所有奇数数的个数。
状态转移方程的原因就不易多说，自己想想就能明白。
T3：有3行，每行N个数，要求你去掉至少多少列使得最后剩下的3行，每行x个数，每一行的这x个数排序之后都一模一样。
模拟。简单模拟。简简单单的模拟。
但是考试竟然没想到，醉了。
因第一行每一个数只出现了一次，所以我们可以先看每一列的第一个数，如果当前第一个数在第二、三行都没有，则这个数不能出现，则把这列删掉。以此类推，一直到不能删列为止（每次删完n列，都要重头开始继续删，直到不能删，因为你删了一列，可能删的列当中的某个数又会引起新的错误）
T4：指有n个区间，如何选择这n个区间，使得最大的区间包含次大，次大包含次次大……以此类推。要求选择的区间数目最多。
很明显，我们可以先把他排个序，我们先把第一个数作为第一个关键字，第二个数作为第二关键字。在使得第一个关键字尽量小的情况，也要使得第二个数靠前的尽量大。
我们知道，当我们排完序之后，就可以在第二个数列里面寻找一个最长不上升子序列。
当然——我们知道寻找最长不上升子序列的办法就是O(n²)，所以如果我们用O(n²)的原始方法就会时间超限。
所以——我们要对其进行优化。
我们可以先建立一个biao，在枚举第i个数的时候，我们从后往前寻找，然后找到一个满足条件——第i个数小于<=biao[j]的，则把biao[j+1]赋值为第i个数，然后~一定要break！（否则时超）但是，如果我们一直找不到一个满足条件的数的话，则可以把长度+1，然后记录在当前新长度的位置……以此类推，最后数列biao的长度就为最终的答案
（我们这里寻找“满足条件”的时候，一定不能从1往len搜，因为这样子的话，即使用了break，也会因为数据的情况导致时超）
现在来解释一下这个优化的原因。
例如数据：
1 1 1 1 2 3
4 5 6 7 5 5
排完序后变成
1 1 1 1 2 3
7 6 5 4 5 5
所以我们只需看7 6 5 4 5 5，这个序列。
首先，我们把7放到biao[1]，然后因为6<=7，所以把长度+1，biao[2]=6，然后5又小于，6，7，又把biao[3]=5，然后4又小于等于前面的每一个数，再把biao[4]转化为4，随后跟随的5因为<=biao[3]所以，把biao[4]变成5，然后最后的5又小于等于前面的每一个数。
所以最后的biao=7 6 5 5 5
长度为5，输出5.
（这就是整个模拟的过程）
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
