上上周做过的题目，1067 和 1024

最近实在太忙，项目里面的一个BUG经常要解很长时间，而且环境也比较恶劣。又有很多自己不能掌控的事情。所以最近也没有做题目。
上次的题目是PKU 1067，一个博弈方面的题目，题目很有意思。记录一下我的思路：
首先题目有一个很大的提示就是棋局都是可解的（就是对于一个棋局，谁会赢是确定的）。首先很容易找到一些必赢的棋局，比如：(1,2), (3,5)(4,7).看看是否有什么规律。对于当前棋局，总能找到一个下法，是的对手无论如何下棋，我都是能赢（递归），或者是，当前棋局，无论如何下棋，对手都能找到下法能赢。

不过规律似乎不是那么容易找到，但是从题目的规则上，容易找到一个筛选算法（带一点贪心性质）。从首先，定义函数 F(a, b）为棋局的胜负(1胜0负，这个胜负代表一种必胜和必负）， C(a, b)为一个规则下法所导致的棋局的集合，比如C(1, 2)就有: (1 , 1), (0, 1), (0, 2), (0, 0)...等（规则就是题目里面的一次只能取一边的任何数目，或者两边都取相同的数目）。那么对于个棋局 (a, b), 通过规则反推， 有：

F(a,b) = 0, 则F(a + x, b + x) = 1
F(a,b) = 0, 则F(a + x, b) = 1
F(a,b) = 0, 则F(a , b + x) = 1

于是：从F(0, 0)为输，那么F(0, 1), F(0, 2),...F( 1, 1), F(2, 2)....F(1, 0), F(2, 0)为赢（显然）。
那么是否可以找到下一个输F(a, b), 是不是把这些筛了下一个就是呢，的确，容易证明：
因为下一个（定义下一个为，b + 1，因为一次筛选肯定能筛掉所有当前行, a 从左到右选择第一个空白）因为下一个F(a,b),通过规则下法，（无论如何，不能不下）， 所以任何 F(c <= a, d <= b) 的棋局是在晒选过得集合里面。F(a,b),通过规则下法，（无论如何，不能不下）， 所以任何 F(c <= a, d <= b) 的棋局是在晒选过得集合里面。这里化个图是很简单的： 这图就是每次筛选用的不同颜色。
因此，如果范围不大，用这个筛选法就能得到结果，可是，这些必胜棋局确实有规律的，我只找到他们的口每次+1，我可怜的思路到此为止，题目中的范围很大，必须找到规律。
后来GOOGLE了，实在想不到了，这个题目的原本就是一个博弈问题，叫做Wythoff 博弈。必胜棋局是有一个通项公式的，BT...

A_n = floor(nP) and B_n = floor(nP) + n, where P = (1+sqrt(5))/2(黄金分割)

好了，到这一步，代码也没什么了。。。


第二题是PKU 1024. 是一个怪绕人的题目，通过迷宫路线求迷宫和多余墙壁。我没想到那个广搜+逐个移去墙壁也能AC。。。
其实我也有一个深搜的版本，深搜的版本预料之中是TLE, 广搜要好很多。，不过可能题目的数据量不大，本来在求墙壁多余的时候，是因该维护一个可“回朔”的队列要好些，因为一个墙壁在广搜的过程中，蔓延到他之前的搜索都是不变的，如果把它移去的话，那么这些层次的数据是应该保留，只用从考虑它开始的那一层广搜开始就行了。另外，有些墙壁天然就是有用的，比如双面路线的，就是不用搜索就可以剔除。不过这些我都没写，就写了个简单的直接搜，竟然AC了，而且16MS还挺快的。。。可能前面有个简单的优化其了一点左右，就是路径的合并，因为题目要求唯一路线，普通广搜只能搜出一条最佳路线，如果要求解所有路线，可能要对兄弟节点都展开，但是实际上可以吧兄弟合并，加入一个ENTER计数,这样就不用重复考虑兄弟又不失路径是否唯一的标志，丢失的只是路径本身（这个信息是不需要的。嘿嘿）。这个题目比较顺利，不若第一个题目那么BT。。

合肥 家乐福

周五下班回家的时候，大概七八点的样子，801路车到青阳路突然改道转金寨路。长江路三里庵段有很多警车。原来是预料之中的抵制家乐福示威活动正式开始了。
星期天接待一个很久没来的朋友，路过长江路，突然一大群人打着标语，喊着口号沿路冲了过去。

以上是我知道的所有的关于合肥家乐福抵制活动的记录。

后来上网，发现合肥的抵制游行活动，无论规模还是影响力，遥遥领先于其他城市。

在此表达一下我的心愿。

尊重自己的同胞，尊重别人的爱国方式，无论形式上还是内容上。请千万不要把拳头挥向自己的同胞，谣言自然不攻自破，但是也要注意若干脑子进水，或者天生暴力倾向，或者别有用心的人。言论自由，不仅仅是对zf的要求，也是对我们自己的要求，当一群人拥有了人数优势，和zf一样，就拥有了一定的暴力，所谓道德制高点的优势，这个时候如果言论的自由被凶恶的打压，和所谓zf的打压没有任何的区别，还显得更加卑劣。

不要沉溺这种大规模活动的表面强势，这毕竟是弱者展示强势的最后手段。做好自己，多多思考，文化，价值观的强势，才是真正的强大。为什么外国的媒体可以侮辱我们，而我们却不能发出自己的声音，为什么外国人看到照片上有坦克和人就会激动。为什么Made in china被外国人肆意歪曲，为什么那么多的科研作假。。。中国的未来，不仅仅是奥运!

好用不经用 ，EG.

上上个星期买了一块EG, 正反狂3. 一个星期就适应了，比OC更适合我。 但是，今天重新刷一遍胶水，面材就脱落了一小块。。。。 真不经用。郁闷。

Blogger里面插代码

Blogger的HTML编辑器插入C代码比较麻烦,得加一个pre，但是pre也不太方便。真是的。不知道有什么好的办法。直接从本地编辑器复制出来的代码粘贴到Blogger就乱七八糟的，自作主张的做了各种排版。不知道在哪里去调整。 晚上去和表弟喝酒，这次的做题先就不写了，和下次的题目一起写。 唉，周末真无聊，自从英超被买断，再也没看过英超，意甲周末也是不一定有，西甲太晚，看球是没什么指望了。要不再去打大波罗？以前在学校是联机玩，单机我玩了一个死灵，到地狱打不动了，全招的，累死了。去玩个法师好了。

北京奥运

本来我对北京奥运没什么特别的感觉。但是最近的关于奥运的事件，打上ZD事件的烙印，觉得奥运对于中国，开始有了某种特殊的意义。这次ZD事件和奥运的风波，在中国，无论各方都在重新思考，世界和中国。

真的没玩够

我最不后悔的事情，和某些人比较，就是在大学的时候选择的是玩的路线，嘿嘿。真的很开心，现在工作了才觉得好明智，如果大学没玩，工作后就没有什么玩的意思了。 很庆幸的是，我到大学之后，电脑已经开始普及，高中的时候电脑游戏就开始兴起，不过大学之后，游戏更呈“专业化”发展。所以，玩的主题基本就是游戏了。其他的，于前辈人共有的比如喝酒唱歌之类，自然不在话下。无论何时，总能找到一帮子人，和你玩。大学三个班，第一年和三班玩，第二年和一班玩，第三年和一班玩，第四年和二班玩。 工作后，身边的朋友逐渐远走了，也没人可以玩了。生活真的黯淡了很多，也许有些人会说，玩够了，该干正经的了，或者说，年纪不小了，该收了。可是我怎么总是觉得没有玩够啊，现在每天没有人一起玩游戏，的确没什么时间，可是觉得现在这样是在浪费生命。 每天回去我都只能在cs,sc两个老游戏里面殴电脑，把他们想像成曾经的同学。。。 。。。 生命在于玩乐。

第三题很失败，1015。

妈的， space速度还真不是一般的慢，还是用我的blogspot好了，虽然国内无法访问。 这周做个题目不顺，就是那个1015,陪审团问题。虽然有个思路，但是因为实在没有时间去做，没有提交，因为老是没作对。 思路是类似动态规划。貌似不能叫做动态规划来解的题，因为题目的最优解并不是通过求解相同最优子结构来做的，而是通过相同子结构迭代求一系列解来做。求和问题和01背包很类似，有大量同子问题。通过增长决策的源数据下标，增长求和个数（<=20），不断求得一个范围内的和数问题。然后选择最优的。因为没有用去尝试这个解法（空间复杂度比较高，而且用C写，存路径很麻烦的，debug也要费不少时间），所以不敢保证是对的，也不想再纠缠下去。 Bs自己。 后来在《算法导论》的NP完全问题的近似解法中也看到一个类似的算法求子集和数的问题（不过这个和数是固定的，子结构中超过这个和数就可以cut掉，解法没什么，但是那个通过归并排序来求下个决策下标的和数比较不错），书上没说这个是属于动态规划，俺也不敢说。虽然真的和动态规划很像。

第二题1175和一些思考

第二题本来是乱选一个题目是个求解同棋局问题，但是我觉得题意有点不清晰。（到底是形状匹配还是下法匹配），打开discuss，有人说数据有问题，很容易pass,另外一个人说和1175题目完全一样，我就去做了1175。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1175

1175是个很浪漫的题目，求解星空中所有相同的星簇（cluster）。 (98 IOI). 这个题目乍一看相当简单，但是做起来发现也是很容易出错的。
我的结果是16MS。未作更多优化。
思路很简单，先逐个查找出所有的星簇，当找到一个星星就从她开始递归的连接出所有的其他星星，存储宽，高等足够的信息。
然后从已经找到的星簇中寻找相同的，旋转和倒映的，如果没有找到就继续。找到了，要把星星标记重新标记为已经存在的那个字符。这里我对于旋转和映射没有使用公式而是使用一个scanner函数表，不同的方向各自一个，本质上就是对于源的一个scan顺序，目标只要使用scanner表离得任何一个通过检测就OK了。里面没用公式，推导公式我觉得不如组织好的代码更不容易出错。而且效率差不多。而且当时觉得scanner的状态可能对后面解题有帮助。（其实没有-_-!）

过了题目中的简单数据，提交上去，立刻WA...

（总是在拉屎的时候思路稍微清晰），如果两个相同的星系相互侵入，那么直接通过标记来判断就不对了，必须保留星星属于哪个星系的信息，否则再重标记之后就会导致以后的检测错误。简单了，再加个数组，存储星tag为他们所在星簇的idx.

OK。过了。
对于效率，因为数据量很小，并没有去做一些一优化，稍微加了一个星星总数判断，但是没有什么改观。
但是如果数据量很大，有一点值得思考，类似KMP的字符串普配算法，对于星系的匹配判断是可以做优化的：
就是一个方向的检测失败，这个结果是可以使用到其他方向的，而且这个因素是这个星簇自己的属性。因此可能有这么一个算法:

当方向d1测试失败，所处scanner的位置（简单起见，用其中一个整数，行）i,有：
此时i之前的数据都是已知的，那么就会有一些方向不需要再匹配，另外一些方向只需要从某个scanner位置开始匹配。这个信息可以作为:
f(d1, i, d2) =
{
   = -1 :不可能匹配
   or d2 scanner的起始位置 (i,j)。
}//d2是新的一个方向


那么每当得到一个cluster,就可以求出这个f的集合。可以自己和自己匹配得到。
比如：
[XXXXXX]
[XXXXXX]
[------]
[VVVVVV]
[VVVVVV]
x和v表示某两个方向的匹配成功，那么对x的来说，一次匹配失败如果在-----，那么到v的方向在匹配只需要到----
开始，如果在XXXXX就完蛋了，那么V也没必要比较。

这样做要增加空间复杂度来存储这些信息。降低星簇查找形同的匹配算法的时间复杂度常数因子。但是对于数据量很小，感觉得不偿失，自己和自己的匹配也是要时间的。这个想法也是一个粗糙的，没去实现，工作比较忙，也没什么时间

#include "stdio.h"

#define MAX_STAR 160
#define MAX_CLSTR 501
#define DIR_NUM 8
#define MAX_W   101
#define MAX_H   101

static char sky[MAX_H][MAX_W];
static int  tag[MAX_H][MAX_W];
static int w;
static int h;
   

typedef struct cluster_t
{
    /*int x[MAX_STAR];
    int y[MAX_STAR];*/
    int start_c;
    int start_l;
    int end_c;
    int end_l;

    int num;
   
    int  idx;
    char mark;
}TCluster;

typedef int (* _scanner_check_dir_fct)(TCluster * c1, TCluster * c2);
typedef int (* _scanner_step_dir_fct)(
    int *pi, int *pj, int sc, int ec, int sl, int el);

TCluster clusters[MAX_CLSTR];
int clusters_count = 0;

static int
simlar_check_star(
   TCluster * c1, int i1, int j1, TCluster *c2, int i2, int j2)
{
    return (      
                    (tag[i1][j1] == c1->idx && tag[i2][j2] == c2->idx)                  
               ||   (tag[i1][j1] != c1->idx && tag[i2][j2] != c2->idx)
              
           );
}




static int
_scanner_check_dir_wh(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == w2 && h1 == h2 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_check_dir_hw(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == h2 && w2 == h1 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_step_dir_lrtb(int *pi, int *pj, int sc, int ec, int sl, int el)
{
   
    (*pj)++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_rltb(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj)--;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_lrbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) ++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_rlbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) --;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}


static int
_scanner_step_dir_tblr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_btlr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_tbrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_btrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



/*l:0, c:1*/
static int _scanner_start[DIR_NUM][2] = {
    {0, 0},
    {0, 1},
    {1, 0},
    {1, 1},
    {0, 0},
    {1, 0},
    {0, 1},
    {1, 1}};



static _scanner_step_dir_fct _scanner_step_funcs[DIR_NUM] = {
    _scanner_step_dir_lrtb,
    _scanner_step_dir_rltb,
    _scanner_step_dir_lrbt,
    _scanner_step_dir_rlbt,
    _scanner_step_dir_tblr,
    _scanner_step_dir_btlr,   
    _scanner_step_dir_tbrl,
    _scanner_step_dir_btrl
};

static _scanner_check_dir_fct  _scanner_filter_funcs[DIR_NUM] = {
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw
};


static int
is_same(TCluster * c1, TCluster * c2, int * pdir)
{
    int dir;
    int i1, j1;
    int i2, j2;

  

    for(dir = 0;  dir < DIR_NUM; dir ++)
    {
        if(_scanner_filter_funcs[dir](
            c1, c2) == 0)
        {
            continue;
        }
        i2 = (_scanner_start[dir][0] == 1)?(c2->end_l):(c2->start_l);
        j2 = (_scanner_start[dir][1] == 1)?(c2->end_c):(c2->start_c);

        for(i1 = c1->start_l; i1 <= c1->end_l; i1 ++)
        {  
            for(j1 = c1->start_c; j1 <= c1->end_c; j1 ++)
            {              
                if(simlar_check_star(c1, i1, j1, c2, i2, j2))
                {
                    _scanner_step_funcs[dir](
                        &i2,
                        &j2,
                        c2->start_c,
                        c2->end_c,
                        c2->start_l,
                        c2->end_l);
                    continue;
                }
                else
                {
                    goto LB_NextCheck;
                }
              
            }           
        }
        *pdir = dir;
        return 1;
LB_NextCheck:;
    }

    return 0;
}


static void
remark_as_old(TCluster * clstr, int curmark, int oldmark)
{
    int i;
    int j;
    for(i = clstr->start_l; i <= clstr->end_l; i ++)
    {
        for(j = clstr->start_c; j <= clstr->end_c; j ++)
        {           
            if(sky[i][j] == curmark && tag[i][j] == clstr->idx)
            {
                sky[i][j] = oldmark;
            }
        }
    }
    clstr->mark = oldmark;
   
}

static int
find_and_merge_cluster(int c_idx)
{
    int i;
    int dir;
    TCluster * clstr;
    TCluster * old_clstr;

    clstr = clusters + c_idx;
   
    for(i = 0; i < c_idx; i ++)
    {
        old_clstr = clusters + i;
        if(is_same(old_clstr, clstr,  &dir) == 1)
        {
            remark_as_old(clstr, clstr->mark, old_clstr->mark);
            return 1;  
        }
    }
    return 0;
}


static void
build_cluster(int c_idx, int i, int j, char cur_mark)
{
    if(i <>= h || j >= w)
    {
        return;
    }

    if(sky[i][j] == '1')
    {
        sky[i][j] = cur_mark;
        tag[i][j] = c_idx;
        clusters[c_idx].num ++;
      
        if(i < clusters[c_idx].start_l)
        {
            clusters[c_idx].start_l = i;           
        }
        if(j < clusters[c_idx].start_c)
        {
            clusters[c_idx].start_c = j;           
        }
        if(i > clusters[c_idx].end_l)
        {
            clusters[c_idx].end_l = i;           
        }
        if(j > clusters[c_idx].end_c)
        {
            clusters[c_idx].end_c = j;           
        }
     
    }
    else
    {
        return;
    }

    build_cluster(c_idx, i - 1, j - 1, cur_mark);
    build_cluster(c_idx, i    , j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j    , cur_mark);
    build_cluster(c_idx, i + 1, j + 1, cur_mark);
    build_cluster(c_idx, i    , j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j    , cur_mark);
}




static void
get_clusters()
{
    int i, j;
    int idx;
    char cur_mark = 'a';
   
    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            if(sky[i][j] == '1')
            {
                idx = clusters_count;

                clusters[idx].mark      = cur_mark;
                clusters[idx].start_c   = MAX_W + 1;
                clusters[idx].end_c     = -1;
                clusters[idx].start_l   = MAX_H + 1;
                clusters[idx].end_l     = -1;
                clusters[idx].idx       = idx;
               
                build_cluster(idx, i, j, cur_mark);
                /*Not found old the same*/
                if(find_and_merge_cluster(idx) == 0)
                {
                    cur_mark ++;
                }

                clusters_count ++;
            }
        }
    }
}

static void
output()
{
    int i;
    int j;

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            printf("%c", sky[i][j]);
        }
        printf("\n");
    }

}

int p_1175_go()
{
    int i;
    int j; 
    char inp;

    scanf("%d\n", &w);
    scanf("%d\n", &h);

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            scanf("%c", &inp);           
            sky[i][j] = inp; 
            tag[i][j] = -1;
        }
        scanf("%c", &inp);
    }
   
    get_clusters();
    output();    
}
int main(void)
{
   
    p_1175_go(1175);
}

BT的第一题

做ACM题计划刚开始就让自己撞了个大钉子，随便选了一个题目，1011，没想到是个超级BT的搜索剪枝题。
Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output

The output should contains the smallest possible length of original sticks, one per line.
Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output

6
5刚看到这个题目觉得还挺简单的，（其实主要原因是有个中文翻译-_-~~). 大概思路就是一开始根据题目的条件有范围确定，接着就是可以回朔搜索了。搜索的时候要剪枝。。.
但是做了就知道根本不是这么简单的。TLE了无数次。
问题的特点就是除了快速求满足一个长度棍子的解之外，还得快速去掉解。
第一个很容易想到的，求解范围，需要整除棍子长度之和，不能小于最大的小棍子长度，个数在小棍子数之内。这些想不到，这题目直接88.
然后搜索的策略，我一开始就走的不对，一开始的方案是让小棍子选择原始棍子的标号搜索，然后剪去原始棍子标号重复。但是这个办法剪枝太难了，因为很容易进入很深的搜索却还对局势没有掌握。放弃。
只能一根根根子去求解，这里面剪枝就多了，棍子排序（自然会想到排序的，快点从大棍子的失败中解脱，并且在后面是的搜索本身呈现顺序性，易于剪枝），然后就是单独原始棍子的后续不要重复的剪枝，还有一个同一长度不在再次使用（在前面排了序，这儿就方便了）的剪枝。有些明显的东西比如长度要刚好满足一个棍子不能叫做剪枝了。上传TLE. TLE. TLE .......
上班比较忙，周末回家才想了一些新办法，但是不知道有些剪枝是不是有问题，最后找到几个可能的剪枝，但是实现起来，代码看着越来越烦了，真不想做了，后来才发现代码里有个保守的错误，这个错误改掉。AC.....大概600MS,虽然不是0MS，我也满意了，痛苦啊。。虽然还有可剪的，但是我已经不想再折磨自己了。
后来才知道1011是个经典的，BT的搜索剪枝题目。
BS 自己。

PS.那个排序用C qsort，速度比泡泡慢 -_~
代码改了很多，看着有点想吐！
#include "stdio.h"

int inp_b[64];
int inp_c = 0;
int min_inp;
int max_inp;
int curL[64];
int curCount[64];

/*int dbg_lay[64][5];*/
int lay[64][64];
int maxC;
int minL;

int used[64];
int usedCount = 0;
static int curSrcIdx;

#define USE(idx)\
do{\
used[idx] = 1;\
curL[curSrcIdx] += inp_b[idx];\
curCount[curSrcIdx] ++;\
usedCount ++;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx] - 1] = inp_b[idx];*/\
lay[curSrcIdx][curCount[curSrcIdx] - 1] = idx;\
}while(0)
#define UNUSE(idx)\
do{\
curL[curSrcIdx] -= inp_b[idx];\
used[idx] = 0; \
curCount[curSrcIdx] --;\
usedCount--;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx]] = 0;*/\
lay[curSrcIdx][curCount[curSrcIdx]] = 0;\
}while(0)

static int tryloop2(int lastIdx)
{
int idx;
int last = 100000;
int ret;
  
if(inp_c - usedCount < idx =" lastIdx;" last =" inp_b[idx];" cursrcidx ="="" ret =" tryloop2(lay[curSrcIdx" cursrcidx ="="" ret ="="" ret ="tryloop2(idx))" ret ="="" i =" 0;" i =" 0;" usedcount =" 0;" cursrcidx =" 0;"> *((int *)p2) )
{
 return -1;
}
else if(*((int *)p1) < *((int *)p2))  {   return 1;  }  else   {   return 0;  } } void b_sort(int inp_b[], int inp_c) {  int i;  int j;  int t;  for(i = inp_c - 1; i >= 0 ; i --)
{
 for(j = 0; j <> inp_b[j])
  {
   t = inp_b[j + 1];
   inp_b[j + 1] = inp_b[j];
   inp_b[j] = t;
  }
 }
}
}
int main(void)
{

int i;


int s = 0;


while(1)
{
 scanf("%d", &inp_c);
 if(inp_c == 0)
 {
  return 0;
 }

 for(i = 0; i < s =" 0;" max_inp =" 0;" min_inp =" 100;" i =" 0;"> inp_b[i])
  {
   min_inp = inp_b[i];
  }
  if(max_inp < max_inp =" inp_b[i];" maxc =" inp_c;"> 0; maxC --)
 {
 
  if(s % maxC == 0)
  {
   minL = s/maxC;
   if(minL < max_inp)
   {
    continue;
   }
  
   //An possible minL;
   if(start_tryloop() == 1)
   {
    break;
   }
  }
 }
}
}

在Linux下面开发GL

自从开始用DFB重新实现GL,但是终于要到目标平台上面做Porting,效果很差，问题很多。这段时间都很忙。看得很紧，今天终于出来界面了，但是问题太多了。Linux和以前的嵌入式的OS差距太大了。首先问题就是地址，以前的地址都是没有用户空间和内核空间的区别，现在有了，问题就出来了，关键是以前留下的代码很难更改。加上要实现的接口是一个用了好几年的一个庞大的库，自我有对下面Driver的依赖，转接到DFB上面也是相当的麻烦的扭捏。 这段时间到时真的学了一点点Linux开发，不过到现在Linux命令还不熟，真倒。