test20190812 Solution

T4 电话线

算法1:
(by LC)
这题数据范围n <= 12, 我一开始以为是状压DP, 但感觉有后效性(其实是本人实力不够), 所以只好放弃。

于是又想了下贪心邻项微扰(基于排序的贪心思想), 搞不出不等式, 也只能作罢。

如果我们用全排列DFS做的话, 能解决n <= 10左右的数据范围。 但是数据可能是没有梯度的。

所以只能玄学了, std::random_shuffle(); 这个函数是用来打乱数组元素顺序的。 我们可以得到这样一个解法: 循环若干次, 得到若干个顺序后再取min。 很玄学对吧? 我循环了10000次, 74分。 循环250000次就AC了。 我因为考试时没有大数据所以不能确定最大的循环次数。 其实用time()是可以的, 但我不会(太弱了)。????

最后理下思路, 循环确定顺序 + 模拟。

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 13;
int F[N], Fr[N][N], Loc[N], n, Ans = 0x7fffffff; 

int main() {
    freopen("haywire.in", "r", stdin);
    freopen("haywire.out", "w", stdout);
    
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= 3; j ++) {
            int F;
            scanf("%d", &F);
            if(F < i) Fr[i][++Fr[i][0]] = F;
        }
    for(int i = 1; i <= n; i ++) F[i] = i;
    for(int i = 1; i <= 250000; i ++) {
        int tap = 0;
        
        std::random_shuffle(F + 1, F + 1 + n);
        for(int i = 1; i <= n; i ++)Loc[F[i]] = i;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= Fr[i][0]; j ++)
                tap += abs(Loc[i] - Loc[Fr[i][j]]);
        
        if(tap < Ans) Ans = tap;

    } return printf("%d\n", Ans) & 0;
}

算法2:dp

上面说到,dp可能会有后效性,这里写下boshi教给我们的dp思想,代码在后日补上。

首先,可以想到:

         /-------|--------/
_______/_________|_______/___________
                 x

(灵魂抽象图上线)

依照上图,通过竖线x有一根电话线,在x的左边,无论排列的顺序是怎样的,都一定只会有一根电话线通过x。

但这就会引出一个问题:通过电话线数量一定,但通过电话线的长度会随左边排列的变化而变化。

所以我们可以将电话线切开(不是字面意思上的切开)成长度为1的部分,如图


         /------|-|-|-------/
_______/________|_|_|______/___________
                 x

这样,我们就只需要考虑通过电话线的多少了,所以我们使用二维的dp,dp当前位置=左边通过电话线和,然后向右走,转移状态。

状态转移方程与代码懒得写先不放

Last modification:August 12th, 2019 at 10:16 pm

Leave a Comment