关于循环展开时间复杂度
  • 板块灌水区
  • 楼主Controls_Wish
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/22 17:12
  • 上次更新2024/8/22 20:16:03
查看原帖
关于循环展开时间复杂度
456678
Controls_Wish楼主2024/8/22 17:12

在一道站外题中

这种写法:

        dp[p][0]=max(max(dp[p-1][2]+b[i][0][0],dp[p-1][1]+b[i][1][0]),dp[p-1][0]+b[i][2][0]);
        dp[p][1]=max(max(dp[p-1][2]+b[i][0][1],dp[p-1][1]+b[i][1][1]),dp[p-1][0]+b[i][2][1]);
        dp[p][2]=max(max(dp[p-1][2]+b[i][0][2],dp[p-1][1]+b[i][1][2]),dp[p-1][0]+b[i][2][2]);

比这种写法(在题目中等价)

        for(int t=0;t<=2;t++){
            dp[p][t]=0;
            for(int x=0;x<=2;x++)
                for(int y=0;y<=2-x;y++)
                    dp[p][t]=max(dp[p][t],dp[p-1][x]+b[i][y][t]);
        }

快一倍(下面的写法会T)

这是为什么呢?

2024/8/22 17:12
加载中...