携程2018春季招聘编程题 - 后台开发

1. 乘积最大

题意

有一个整数n，将n分解成若干个不同自然数之和，问如何分解能使这些数的乘积最大，输出这个乘积m

思路Ⅰ - dp

想到一个比较笨的dpdp，dp[i][j]dp[i][j]表示i分解的最大一个数为j时能分解的最多的数，last[i][j]last[i][j]表示当前状态的次大数，然后找出能分解的最多的数的路径计算即可得到答案，如果能分解的最多的数一样，则找最大数最小的（因为此时所有数相差最小，即乘积最大，由均值不等式可得）。

代码

#include <cstring>
#include <iostream>
using namespace std;
int num, dp[53][53], last[53][53], cnt, rem, tmp;
long long ans;
int main(){
   while(cin >> num) {
       memset(dp, -1, sizeof(dp));
       for(int i = 1; i <= num; ++i) {
           dp[i][i] = 1;
           last[i][i] = 0;
       }
       for(int i = 2; i <= num; ++i) {
           for(int j = 1; j <= i; ++j) {
               if(dp[i][j] != -1) {
                   for(int k = j + 1; i + k <= num; ++k) {
                       if(dp[i + k][k] < dp[i][j] + 1) {
                           dp[i + k][k] = dp[i][j] + 1;
                           last[i + k][k] = j;
                       }
                   }
               }
           }
       }
       cnt = 1;
       rem = num;
       for(int j = 1; j < num; ++j) {
           if(dp[num][j] > cnt) {
               cnt = dp[num][j];
               rem = j;
           }
       }

       ans = 1;
       while(num > 0) {
           ans *= rem;

           tmp = num;
           num -= rem;
           rem = last[tmp][rem];
       }
       cout << ans << "\n";
   }
   return 0;
}

思路Ⅱ - dp

结束后看了题解，才注意到dp[i][j]dp[i][j]表示i分解成的数最大为j时的最大乘积，然后直接进行转移，即可求出答案。这样设状态很方便，环境和心情影响真是太大了。。。

代码

#include <cstring>
#include <iostream>
using namespace std;
int num, dp[53][53], last[53][53], cnt, rem, tmp;
long long ans;
int main(){
   while(cin >> num) {
       memset(dp, -1, sizeof(dp));
       for(int i = 1; i <= num; ++i) {
           dp[i][i] = 1;
           last[i][i] = 0;
       }
       for(int i = 2; i <= num; ++i) {
           for(int j = 1; j <= i; ++j) {
               if(dp[i][j] != -1) {
                   for(int k = j + 1; i + k <= num; ++k) {
                       if(dp[i + k][k] < dp[i][j] + 1) {
                           dp[i + k][k] = dp[i][j] + 1;
                           last[i + k][k] = j;
                       }
                   }
               }
           }
       }
       cnt = 1;
       rem = num;
       for(int j = 1; j < num; ++j) {
           if(dp[num][j] > cnt) {
               cnt = dp[num][j];
               rem = j;
           }
       }

       ans = 1;
       while(num > 0) {
           ans *= rem;

           tmp = num;
           num -= rem;
           rem = last[tmp][rem];
       }
       cout << ans << "\n";
   }
   return 0;
}

2. 通过考试

题意

拼图，是一个老少皆宜的益智游戏，在打乱的3*3的范围中，玩家只能每次将空格(0)和相邻的数字格（上、下、左、右）交换，最终调整出一个完整的拼图。

完整拼图为：

1 2 3

4 5 6

7 8 0

思路 - BFS

C++C++给的空间非常小，所以为了避免MLEMLE，就用了A∗A∗算法，结果写搓了。。。结果一改就成MLEMLE，官方提供的模版简直就是坑人，应该坚定地按照自己的想法写。

最后换成intint就ACAC了

代码

#include <iostream>
#include <map>
#include <queue>

using namespace std;

const int dx[] = {-3, 1, 3, -1};

struct Node {
   int status, cnt;

   Node() {}

   Node(int sstatus, int ccnt): status(sstatus), cnt(ccnt) {}
}cur;

int index, tmp, status, dir;
map<int, bool> mp;
queue<Node> q;
int goal = 123456789;
int s[11];

void getDir() {
   dir = 0;
   if(index > 2) {
       dir |= 1;
   }
   if(index % 3 != 2) {
       dir |= 2;
   }
   if(index <7) {
       dir |= 4;
   }
   if(index %3 != 0) {
       dir |= 8;
   }
}

int bfs(int numbers) {
   q.push(Node(numbers, 0));
   mp[numbers] = true;
   while(!q.empty()) {
       cur = q.front();
       q.pop();
       if(cur.status == goal) {
           return cur.cnt;
       }

       for(int i = 8; i >= 0; --i) {
           s[i] = cur.status % 10;
           if(s[i] == 9) {
               index = i;
           }
           cur.status /= 10;
       }
       getDir();
       for(int i = 0; i < 4; ++i) {
           tmp = index + dx[i];
           if(((dir & (1 << i)) != 0) && 0 <= tmp && tmp < 9) {
               swap(s[index], s[tmp]);
               status = 0;
               for(int j = 0; j < 9; ++j) {
                   status = status * 10 + s[j];
               }
               if(!mp[status]) {
                   q.push(Node(status, cur.cnt + 1));
                   mp[status] = true;
               }
               swap(s[index], s[tmp]);
           }
       }
   }
   return -1;
}

int main() {
   status = 0;
   for(int i = 0; i < 9; ++i) {
       scanf("%d", &tmp);
       if(tmp == 0) {
           tmp = 9;
       }
       status = status * 10 + tmp;
   }
   printf("%d\n", bfs(status));
   return 0;

}