题目原型:
给出N个元素,每个元素具有3个属性,称为属性A、属性B和属性C。方便起见,我们用Ai, Bi, Ci来表示第i个元素的属性A、B、C。
你的任务是,把全部元素分为3个集合(可以为空),称为集合X、集合Y和集合Z,使表达式max_(i∈X)⁡{A_i }+max_(i∈Y)⁡{B_i }+max_(i∈Z)⁡{C_i }的值最小。
题解:
从大到小枚举集合X的最大值,考虑怎么维护划分成两个集合的最小值。可以发现如果有B1 < B2且C1 <C2则元素(B1, C1)无用。因此可以用平衡树维护一个Bi值递增,Ci值递减的序列,此时最优值等于Bi + Ci + 1。时间复杂度是O(N log N)。
flagleaf 解题报告
By Nettle
1、搜索
DFS(Now_Time, Now_Score, Now_Opt);
Now_Time 当前时间,当Now_Time = Time_Limit 时更新当前最优值。
Now_Score 当前得分
Now_Opt 包含K个元素的一个一维数组,当前存在仙器的位置。
枚举从Now_Opt可以到达的Next_Opt,进行下一步搜索:
DFS(Now_Time + 1, Now_Score + This_Time_Score, Next_Opt);
剪枝:
1)
若 Now_Score + Max_Rest_Score < Now_Best 则可以剪枝。
Max_Rest_Score = 剩下的每个时间段最大的K个值之和。
2)
对于当前所有的Next_Opt从大到小进行搜索,在一定程度上可以减少枚举量。
时间复杂度:O( C(K, N) * M ^ T );
预计得分:30分
2、朴素DP
由刚刚的搜索可以知道,这道题具有DP的性质,所以我们用DP来做。
K最大为5,N最大为10,所以设计状态 f[Time][p_1][p_2][p_3][p_4][p_5]; (p_i均不相等)
这样空间的开销为 1000 * 10^5 = 10^8,加起来近400M。
因为一个状态只与前一个状态有关,所以可以采用滚动数组,这样空间开销就能够承受了。
时间复杂度:O(TMN^K);
预计得分:50分
3、状态压缩DP_1
还是从数据范围入手,N最大为10,K最大为5。
我们这样想,对于一个岛,如果有仙器我们用1表示,没有怎用0表示。
这样就可以用一个01串表示当前各个岛的状态,共有2^10 - 1个状态。
而两个状态之间的关系用一个bool数组存储,可以通过O(N^2)的预处理完成:
对于两个状态,因为最多只能移动一个仙器,所以可以肯定两个状态之间只有一个1的位置不一样。
比如:
Now 011001
Next 001011
Change 010010
这样只需要判断改变的前后位置是否有桥连接就可以确定是否能够转移。
设bool数组edge[],若存在桥连接i,j,则edge[2^(i-1) + 2^(j-1)] = true。
若edge[ Change ] = true,则可以从Now转移到Next, 而Change刚好就是Now ^ Next(Now xor Next)。
时间复杂度: O(N^2 + T4^N);
预计得分:70分
4、状态压缩DP_2
对于一组给定的数据,实际上的状态数为C(K, N),最多也不过C(5, 10) = 252,而我们处理成了2^N。
所以我们只要消去这些冗余,就可以节省很多时间,最大的数据也能在1000MS内通过。
时间复杂度:O(C(K,N)^2 + TC(K,N)^2);
预计得分:100分
Solution
对于原来的每个串可以分别拆成K+1个串,例如K=1时142536可以变形为123|456,之后求多个串的最长公共子串即可。
对于部分数据可以使用枚举、动规、Hash等方法求解,对于全部数据可以使用后缀树、后缀数组等方法求解。
动态规划题,首先把数据抽象成对于环上的每一个点,求出选这个点的值(等于该点权值)和不选这个点的值(等于该店附着点的权值和),然后动态规划,f[i][j][k](j,k为布尔量)表示选了前i个点之后第一个点是否选取并且第i个点是否选取。