动态规划: 最多航线

描述

有一个国家被一条何划分为南北两部分，在南岸和北岸总共有N个城镇，每一城镇在对岸都有唯一的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城镇都希望有一条航线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉（如果两条航线交叉，将有很大机会撞船）。

你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出现交叉的航线最多。

输入数据

输入文件（ship.in）包括了若干组数据，每组数据格式如下：

第一行两个由空格分隔的整数x，y，10〈=x〈=6000，10〈=y〈=100。x 表示河的长度而y表示宽。第二行是一个整数N(1<=N<=5000)，表示分布在河两岸的城镇对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D〈=x〉，描述每一对友好城镇沿着河岸与西边境线的距离，C表示北岸城镇的距离而D表示南岸城镇的距离。在河的同一边，任何两个城镇的位置都是不同的。整个输入文件以由空格分隔的两个0结束。

输出数据

输出文件(ship.ou)要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数目。

示例

Ship.in

30 4 

7

22 4

2 6

10 3

15 12

9 8

17 17

4 2

0 0

Ship.out

4

分析：

这个题目可以抽象成为最长递增子序列。

对于河岸，宽度是没意义的。

对于一组城镇(a, b)，我们设置一个数组，将a作为数组下标，b作为数组的值，那么，输入可以变成:

input[22] = 4; input[2] = 6; ... ;input[4] = 2

想象一下，整体考虑input数组，显然其下标从0到N递增，如果能保证下标0到N的数组的值是递增的，那么每个数组下标对应的航线（如果存在的话），就可以同时出现而不相交。

问题就变成了就成了数组input 的最长递增子序列。

因此，确定了其值的序列，数组下标就没有意义了。为了减少开销，我们可以简化数组，让这几对值连续存储，用连续的下标表示

下面是递推关系

典型的10背包问题。

设n为数组下标，k为到n为止的最长递增序列的长度，f(n,k)为到n为止，最长子序列长度为k的子序列的最大值。

f(n,k) 的最大递增子序列为 m1,m2...mk， 最大值为mk， f(n,k) = mk

f(n+1,k+1)

如果不存在f(n,k+1),如果input[n+1]>f(n,k),那么input[n+1]可以加入f(n,k)序列后的最后一位，序列变为m1,m2 ...m(k+1),其中m(k+1)为input[n+1];

如果存在f(n,k+1),即存在到n+1为止，长度为k+1的子序列，m1,m2...mk,m(k+1)

f(n+1,k+1)肯定存在  无论n+1元素是不是能够加入到子序列中，都有f(n+1,k+1) = f(n,k+1);  

如果( input[n+1] > f(n,k) 且 input[n+1]>f(n+1,k+1)，那么n+1可以替换序列m1...m(k+1)中的最后一个，替换后的序列最大值为 input[n+1]

典型的10背包问题。

优化：

题目中N最大为5000,所以n,k的最大值都为5000,一个5000*5000的int二维数组,即便能申请成功也是太浪费了。

分析过程，对于f(n+1,k+1)来说，其值只可能是0, input[n+1] 或 f(n,k+1)或，f(n,k)。所以，只需要保存2个大小为6000的数组即可，即f(n,k) ( 0

每轮计算完，可以将f(n,k)丢弃，并用f(n,k+1)替换即可。

复杂度分析。

优化存储结构的时候，其时间复杂度为O(N)

递推时，复杂度为O(n^2/2)

/*
 * =====================================================================================
 *
 * Filename: sealine.c
 *
 * Description:
 *
 * Version: 1.0
 * Created: 10/13/2012 10:13:04 PM
 * Revision: none
 * Compiler: gcc
 *
 * Author: [e-mail] (),
 * Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>

#include <stdio.h>
#include <memory.h>

#define    MAX 6000            /* */


void fill(int input[], int size){
    int len = 0;
    int result[MAX] = {0};
    int i;
    result[0] = input[0];
    for(i = 1; i<size; i++){
        result[i] = result[i-1] > input[i] ? input[i] : result[i-1];
    }
    len++;

    for(;len<size;len++){
        int tmp[MAX] = {0};
        int start = len;
        for(;start<size;start++){
            if(result[start-1] == 0) continue;
            input[start] > result[start-1]? (tmp[start] = input[start]) : (tmp[start] = tmp[start-1]);
            if(tmp[start-1] != 0 && tmp[start-1]<tmp[start]) tmp[start] = tmp[start-1];
            printf ( "len = %d col = %d max = %d\n", len,start, tmp[start] );
        }
        memcpy(result,tmp,sizeof(int)*MAX);
    }

}

int* formatinput(int * input, int size){
    int i = 0;
    int result[MAX] = {0};
    for(;i<size;i+=2){
        result[input[i]] = input[i+1];
    }
    int count = 0;
    int *sresult = (int *)malloc(sizeof(int)*MAX);
    for(i=0;i<MAX;i++){
        if(result[i] != 0){
            sresult[count++] = result[i];
            printf ( "%d ", result[i] );
        }
    }
    printf ( "\n-------------------------\n" );
    return sresult;
}

/*
 * === FUNCTION ======================================================================
 * Name: main
 * Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int input[] = {22,4,2,6,10,3,15,12,9,8,17,17,4,2};
    int *finput = formatinput(input,sizeof(input)/sizeof(int));
    fill(finput, sizeof(input)/2/sizeof(int));
    return EXIT_SUCCESS;
}                /* ---------- end of function main ---------- */

阅读(1230) | 评论(0) | 转发(1) |

0

上一篇：微软面试100题(66):递归颠倒一个栈

下一篇：动态规划(hdoj3006):数字集合