Poj2533 - Longest Ordered Subsequence

Here is my ugly Dynamic Programming solution. On the POJ board they've been talking about DP + binary search, which seems achieves an O(nlgn) time solution, but I've no idea about what it looks like, though.

/**
 * Problem: 2533, Longest Ordered Subsequence
 * User: LoiteringLeo
 * Memory: 4316K     Time: 938MS
 * Language: GCC    Result:
 */
#include <stdio.h>
#define MAX_ELE 1000
int a[MAX_ELE + 1];
int c[MAX_ELE + 1][MAX_ELE + 1];

/**
 * Find the Longest Ordered Subsequence in a given number sequence
 */
int los(int *a, int n)
{
    int i;
    int j;
    int k;
    int longest;
    int curr_longest;

    for (i = 1; i <= n; i++) {
        c[1][i] = 1;
        c[i][i] = 1;
    }

    for (j = 2; j <= n; j++) {
        curr_longest = 1;
        for (i = 1; i < j; i++) {
            for (k = i; k < j; k++) {
                if (a[j] > a[k] && curr_longest < c[i][k] + 1) {
                    curr_longest = c[i][k] + 1;
                }
            }
            c[i][j] = curr_longest;
        }
    }

#if 0
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            printf("%d ", c[i][j]);
        }
        printf("\n");
    }

#endif

    longest = c[1][1];
    for (i = 2; i <= n; i++) {
        if (longest < c[1][i]) {
            longest = c[1][i];
        }
    }
    return longest;
}

int main()
{
    int n;
    int i;

    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    printf("%d\n", los(a, n));

    return 0;
}

 

Multiple External Definitions in C

Look at this code:

/* global1.c */
#include <stdio.h>

int x;

int main()
{
    x = 1;

    printf("%d\n", x);

    return 0;
}

/* global2.c */
#include <stdio.h>

int x;

int getx()
{
    x = 2;
    return x;
}

 

交换两个数组元素使数组元素和的差最小

问题:

给定两个等长的整数数组,数组中元素无序。交换两个数组的元素,使两个数组的和之差值最小。
如A = {1, 2, 3, 4}, B = {5, 6, 7, 8}
输出:A = {2, 3, 5, 8}, B = {1, 4, 6, 7}
 
我的做法:思路来自http://hi.baidu.com/gropefor/blog/item/231f1439727cbe33b8998f18.html,也是一种笨办法。但我在枚举之前对数组进行排序,在适当的时候就能判断出一次循环可以结束。以此换回一些不必要的循环时间。

Rediscovering Ubuntu 10.04 - Part II

 

It was months since I posted "Rediscovering Ubuntu 10.04". As was stated, Ubuntu 10.04 in general is convenient to use, possibly after some tweaking for an advanced level user. I also had terrible experience with that evil GRUB2, which came out to be unstable on systems previously have GRUB installed.
 
In the past days, there're pieces of tips accumulated and I'm eager to share them here.
 
First and most important one, the GRUB2 didn't work correctly on my old desktop which had GRUB installed previously. Sometimes the machine booted into Ubuntu but reset before entering the system, sometimes it hang in grub rescue> prompt which didn't accept input at all, still some times it threw out "grub_puts not found" and stopped there. 1 in 10 times I could boot into Ubuntu normally though. To me this was a big fortune, because I had a chance to change it. For guys who had no possibility getting into the system it was a complete tragedy. OK. People say (The GRUB2 Guide), 'If you can get to a normal installation, run the grub-install command or use the "dpkg-reconfigure grub-pc" command to put Grub onto your current partition.' So I did, and the bug seemed went over.
 

How LD_PRELOAD Affects Library Load Priority

Mike Ma@is-programmer posted a short article on LD_PRELOAD which I liked pretty much. Googling around I found a further discussion on LD_PRELOAD, which as a final example illustrated a tricky use of this environment variable: by modifying function return address changed excecution path. That example didn't work on my machine though. So to make it work, as well as make further explanation on that, I took some effort to change it. Here it is.

 

Rediscovering Ubuntu 10.04 - I'm lovin' it!

    Ubuntu has done good enough on English versions but still come short on internalization and media play. Ubuntu 10.04 is no exception. For this reason I haven't let it run on my personal computer, but I did run it on working machines. Some day some thing hit me on my brain then I was silly enough to install it on my PC - a Pentium 4 2.8C old brother with 1GB RAM which was upgraded from 512M before long.