你可以吧代码编译了  自己运行  看对头不 ~~~~

如果你还没理解  我建议你加我QQ  我慢慢给你解释~~~（什么是数学里面的构造数~~~~~~）你的第1个问题 我明天给你贴个代码  个人觉得比你的那个好  嘿嘿

你们真的是一叶遮目，第一题就是一DP求解，代码我已经贴了。O(n^2)的效率。你们那贴的能叫代码啊？

32楼：
这样吧，你补全下面的search_same(int arr[], int n);函数的定义：

#include <stdio.h>

int search_same(int arr[], int n);

int main()
{
    int arr[100];
    int i;

    for(i=0; i<100; i++){
        arr[i] = i;
    }
    arr[34] = 58;

    fprintf(stdout, "The same one:%d\n", search_same(arr, 100));

    return 0;
}

上面缺失34，重复58，请写出你的算法找出重复的数58.

33楼：
我编译了你写的程序，用 ，“adbccadebbca”和“edabccadece”测试，得到结果：dbccadec
恩，这个结果是不对的，可以看出来正确的是：bccade 建议你再改改代码，正确了再发上来好吗？

#include <vector>
#include <string>
#include <iostream>

template <typename T>
void LCS(const T& s1, const T& s2, T& s3)
{
    const size_t len1 = s1.size();
    const size_t len2 = s2.size();
    std::vector< std::vector<unsigned int> > d(len1 + 1, std::vector<unsigned int>(len2 + 1));
    std::vector< std::vector<unsigned int> > b(len1 + 1, std::vector<unsigned int>(len2 + 1));
    const int w = 1;
    const int n = 2;
    const int nw = 3;
    for(int i = 1; i <= len1; ++i)
    {
    for(int j = 1; j <= len2; ++j)
    {  
        if (s1[i-1] == s2[j-1])
        {
        d[i][j] = d[i-1][j-1]+1;
        b[i][j] = nw;
        }
        else
        {  
        if (d[i-1][j] >= d[i][j-1])
        {
            d[i][j] = d[i-1][j];
            b[i][j] = n;
        }
        else
        {
            d[i][j] = d[i][j-1];
            b[i][j] = w;
        }
        }
    }
    }
    s3.resize(d[len1][len2]);
    int i=len1;
    int j=len2;
    int k=d[len1][len2]-1;
    while ( k>=0 && i>0 && j>0 )
    {
    if ( b[i][j] == nw )
    {
        s3[k--] = s1[i-1];
        i -- ;
        j -- ;
    }      
    else if (b[i][j] == n)
        i -- ;
    else if (b[i][j] == w)
        j --;
    else
        break;
    }
}
int main(int argc, char * argv[])
{  
    std::string s1("adbccadebbca");
    std::string s2("edabccadece");
    std::string s3;
    LCS(s1, s2, s3);
    std::cout<< s3 <<std::endl;
    return 0;
}

恩  我错了  我原来的代码始终把相同的数放在最后一位上，这样无形中固定了一个变元，所以可以求得出来，但是如果相同数不在最后一位的话 相当于解2个变元， 没办法求解  

我再次编译了你写的程序，还是用“adbccadebbca”和“edabccadece”测试，得到结果：abccadec
恩，这个结果是不对的，可以看出来正确的是：bccade 建议你再改改代码，测试正确了再发上来好吗？

devil求的是最长公共子序列，子序列的定义是“顺序一致的字符序列”，可以分隔来，而LZ的题目要求必须不可分隔，哈哈~~

 哼哼， 懂我的，这里只有几个人而已。

 跟智商低的人，不必要求的太高。

 他也许这辈子都不知道什么是DP.

[ 本帖最后由 Devil_W 于 2010-5-2 17:35 编辑 ]

先给出一个第二题的代码吧：

int search_same(int arr[], int n)
{
    int i, xor = 0, a = 0, b = 0;

    for (i = 0; i < n; ++i)
        xor ^= arr[i] ^ i;
    xor -= xor & (xor - 1);

    for (i = 0; i < n; ++i)
    {
        (void)((i & xor) ? (a ^= i) : (b ^= i));
        (void)((arr[i] & xor) ? (a ^= arr[i]) : (b ^= arr[i]));
    }

    /* notice that onluy one number in a and b is the dupicate one */
    for (i = 0; i < n; ++i)
        if (arr[i] == a)
            return a;
    return b;
}

第一题还在写……好久没写DP了，汗……（其实devil的代码稍微改一点点就可以做第一题了）


[ 本帖最后由 StarWing83 于 2010-5-2 18:06 编辑 ]