搜狗笔试题-白红宇

转自：

搜狗：

1，有n*n个正方形格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右走。一共走两次，把所有经过的格子的数加起来，求最大值。且两次如果经过同一个格子，则该格子的数只加一次。

思路：

搜索：一共搜（2n-2）步，每一步有四种走法。考虑不相交等条件可以剪去很多枝。

复杂度为O(4^n）

动态规划：

by:

详细算法思路：http://www.51nod.com/question/index.html#!questionId=657

s[k][i][j] = max(s[k-1][i-1][j-1],s[k-1][i-1][j],s[k-1][i][j-1],s[k-1][j][i])+map[i][k-i]+map[j][k-j];

复杂度为O(n^3)

1     #include 
      
           2     #define MAX(a,b) (a)>(b)?(a):(b)    3     using namespace std;    4         5     #define N 5    6     int map[5][5]={    7         {
    2,0,8,0,2},    8         {
    0,0,0,0,0},    9         {
    0,3,2,0,0},   10         {
    0,10,0,0,0},   11         {
    2,0,8,0,2}};   12     int sumMax=0;   13     int p1x=0;   14     int p1y=0;   15     int p2x=0;   16     int p2y=0;   17     int curMax=0;   18        19     /*  20     编号系统为：  21     00000  22     11111  23     22222  24     33333  25     44444  26     走1次：编号有：0,1  27     走2次：编号有：0,1,2  28     走5次：编号有：1,2,3,4  29     走k次：编号有：l,l+1,l+2...,h-1 //low,high 的计算见code  30     编号到map坐标的转换为：  31     编号i，则对应map[i][k-i].  32       33     dp方程为：  34     s[k][i][j] = max(s[k-1][i-1][j-1],s[k-1][i-1][j],s[k-1][i][j-1],s[k-1][j][i])+map[i][k-i]+map[j][k-j];  35     */   36     int dp(void){   37         int s[2*N-1][N][N];   38         s[0][0][0]=map[0][0];   39            40         for(int k=1;k<2*N-1;k++){   41             int h = k
       
        =0)   49                             t= MAX(t, s[k-1][i-1][j-1]);   50                         if( j
        
         =0&&j
         
          sumMax)   64                 sumMax = curMax;   65             return;   66         }   67        68         if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))   69         {   70             if( p1x>= p2x && p1y >= p2y )   71                 return;   72         }   73        74         //right right   75         if( p1x+1

2，有N个整数（数的大小为0-255）的有序序列，设计加密算法，把它们加密为K个整数（数的大小为0-255），再将K个整数顺序随机打乱，使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法。

有三个子问题：

1，N<=16,要求K<=16*N.

2，N<=16,要求K<=10*N.

3，N<=64,要求K<=15*N.

本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/archive/2012/12/13/2817039.html，如需转载请自行联系原作者