/favicon.ico

子恒的博客

[算法]逆序对计算的思考

逆序对计算的思考(Tsinghua OJ,PA1) 题目出自清华DSA的Programming Assignment作业灯塔(LightHouse). 描述 海上有许多灯塔,为过路船只照明。 如图一所示,每个灯塔都配有一盏探照灯,照亮其东北、西南两个对顶的直角区域。探照灯的功率之大,足以覆盖任何距离。灯塔本身是如此之小,可以假定它们不会彼此遮挡。 若灯塔A、B均在对方的照亮范围内,则称它们能够照亮彼此。比如在图二的实例中,蓝、红灯塔可照亮彼此,蓝、绿灯塔则不是,红、绿灯塔也不是。 现在,对于任何一组给定的灯塔,请计算出其中有多少对灯塔能够照亮彼此。 输入 共n+1行。 第1行为1个整数n,表示灯塔的总数。 第2到n+1行每行包含2个整数x, y,分别表示各灯塔的横、纵坐标。 输出 1个整数,表示可照亮彼此的灯塔对的数量。 样例 Input: 1 2 3 4 3 2 2 4 3 5 1 Output: 1 1 限制 对于90%的测例:1 ≤ n ≤ 3×10^5 对于95%的测例:1 ≤ n ≤ 10^6 全部测例:1 ≤ n ≤ 4×10^6 灯塔的坐标x, y是整数,且不同灯塔的x, y坐标均互异 1 ≤ x, y ≤ 10^8 时间:2 sec 内存:256 MB 提示 注意机器中整型变量的范围,C/C++中的int类型通常被编译成32位整数,其范围为[-231, 231 - 1],不一定足够容纳本题的输出。 思考 我们把灯塔坐标抽象为坐标结构体 1 typedef struct pos{ long x,y; }Pos; 照亮的情况为一个灯塔在另一个灯塔的一四象限,即$tower1.

[算法]DP解决钢条切割问题

DP解决钢条切割问题 (原题见算法导论·动态规划) 对长度为n的钢条进行切割,对应的切割长度和价格对应如下: int cost[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; 比如1对应价值1,10对应价值30。即相应的下标和值的对应。现求切割所得最大效益mx。 递归算法 1 2 3 4 5 6 7 8 9 int cut_rod(int *cost,int n) { if(n == 0) return 0; int limit = MIN(n,10); //分割第一条的上限 int mx = -1; for(int i = 1;i <= limit; ++i) mx = maxnum(mx,cost[i]+cut_rod(cost,n-i)); //取当前值于递归值的最大值 return mx; } 由于对相同子问题的重复求解,T(n) = 2^n 递归标记数组算法(自顶而下)(DFS) 1 2 3 4 5 6 7 8 9 10 11 12 int mem_cut_rod(int *cost,int n,int *mem) //mem数组长度为n,所有元素须在其他函数中初始化为-1 { int mx; if (mem[n] >= 0) return mem[n]; //对于求过的问题,直接返回存储的值 if (n == 0) mx = 0; else mx = -1; int limit = MIN(n,10); for(int i = 1;i <= limit; ++i) mx = maxnum(mx,cost[i]+mem_cut_rod(cost,n-i,mem)); //后面的内容和递归型是一样的 mem[n] = mx; //储存计算出的新值 return mx; } 逆拓扑序DP(自底向上) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int bottom_cut_rod(int *cost,int n) { int mem[MEM_LEN+1]; //MEM_LEN = n,设置标记数组 mem[0] = 0; //i,j将从1开始,这里收益是0 for(int i = 1; i <= n; ++i) //从第一个问题开始求解 { int mx = -1; int limit = MIN(i,10); for(int j = 1;j <= limit; ++j) mx = maxnum(mx,cost[j] + mem[i-j]); //求解最小的问题 mem[i] = mx; } return mem[n]; } 我们可以看到,2,3 的解法复杂度均为O(n^2)。