阿里Java在线笔试编程题：求解

同样不会……

// POSIX C #include <sys/types.h> #include <sys/wait.h> #include <unistd.h> #include <signal.h> #include <errno.h> #include <fcntl.h> #include <dirent.h> // ANSI C #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> // C++ lib #include <iostream> #include <limits> #include <fstream> #include <vector> using namespace std; int main(){     int N;     cin>>N;     if(N == 0){         cout<<0<<endl;         return 0;     }     vector<int> A(N);     vector<int> B(N);     for(int i=0;i<N;++i){         cin>>A[i];     }     for(int i=0;i<N;++i){         cin>>B[i];     }     vector<vector<int> > d(N+1, vector<int>(N+1, 0));     d[0][0] = 0;     for(int i=1;i<=N;++i){         if(i%2 == 0){             int sum = 0;             for(int j=0;j<i;j+=2){                 sum += A[j]*A[j+1];             }             d[i][0] = sum;         }else{             d[i][0] = numeric_limits<int>::max();         }     }     for(int i=1;i<=N;++i){         if(i%2 == 0){             int sum = 0;             for(int j=0;j<i;j+=2){                 sum += B[j]*B[j+1];             }             d[0][i] = sum;         }else{             d[0][i] = numeric_limits<int>::max();         }     }     d[1][1] = A[0]*B[0];     for(int i=2;i<=N;++i){         if(i%2 == 1){             int min = numeric_limits<int>::max();             if(d[i-1][0]!=numeric_limits<int>::max()){                 min = min<(d[i-1][0]+A[i-1]*B[0])?min:(d[i-1][0]+A[i-1]*B[0]);             }             if(d[i-2][1]!=numeric_limits<int>::max()){                 min = min<(d[i-2][1]+A[i-1]*A[i-2])?min:(d[i-2][1]+A[i-1]*A[i-2]);             }             d[i][1] = min;         }else{             d[i][1] = numeric_limits<int>::max();         }     }     for(int i=2;i<=N;++i){         if(i%2 == 1){             int min = numeric_limits<int>::max();             if(d[0][i-1]!=numeric_limits<int>::max()){                 min = min<(d[0][i-1]+A[0]*B[i-1])?min:(d[0][i-1]+A[0]*B[i-1]);             }             if(d[1][i-2]!=numeric_limits<int>::max()){                 min = min<(d[1][i-2]+B[i-1]*B[i-2])?min:(d[1][i-2]+B[i-1]*B[i-2]);             }             d[1][i] = min;         }else{             d[1][i] = numeric_limits<int>::max();         }     }     for(int i=2;i<=N;++i){         for(int j=2;j<=N;++j){             int min = numeric_limits<int>::max();             if(d[i-1][j-1]!=numeric_limits<int>::max()){                 min = d[i-1][j-1]+A[i-1]*B[j-1];             }             if(d[i-2][j]!=numeric_limits<int>::max()){                 min = min<(d[i-2][j]+A[i-2]*A[i-1])?min:(d[i-2][j]+A[i-2]*A[i-1]);             }             if(d[i][j-2]!=numeric_limits<int>::max()){                 min = min<(d[i][j-2]+B[j-2]*B[j-1])?min:(d[i][j-2]+B[j-2]*B[j-1]);             }             d[i][j] = min;         }     }     /*     for(int i=0;i<=N;++i){         for(int j=0;j<=N;++j){             cout<<d[i][j]<<" ";         }         cout<<endl;     }     */     cout<<d[N][N]<<endl;     return 0; } // 你提交试试，个人感觉好难，想了整晚。。。

class State: def __init__(self, x, y, sum): self.x = x self.y = y self.sum = sum def __str__(self): return 'x=%d y=%d sum=%d'%(self.x, self.y, self.sum) class Solution(object): min = float('inf') def forward(self, a_list, b_list, prev_state): s1_min, s2_min, s3_min = float("inf"), float("inf"), float("inf") a_len = len(a_list) b_len = len(b_list) s1, s2, s3 = None, None, None for state in prev_state: if state == None: continue if [state.x, state.y] == [a_len-1, b_len-1] and state.sum<self.min: self.min = state.sum if (state.x+2 < a_len) and (state.sum + a_list[state.x + 1] * a_list[state.x + 2] < s1_min): s1 = State(state.x + 2, state.y, state.sum + a_list[state.x + 1] * a_list[state.x + 2]) s1_min = s1.sum if (state.x+1 < a_len) and (state.y+1 < b_len) and (state.sum + a_list[state.x + 1] * b_list[state.y + 1] < s2_min): s2 = State(state.x + 1, state.y + 1, state.sum + a_list[state.x + 1] * b_list[state.y + 1]) s2_min = s2.sum if (state.y+2 < b_len) and (state.sum + b_list[state.y + 1] * b_list[state.y + 2] < s3_min): s3 = State(state.x, state.y + 2, state.sum + b_list[state.y + 1] * b_list[state.y + 2]) s3_min = s3.sum return [s1,s2,s3] def min_sum(self, a_list, b_list): prev_state = [State(-1,-1,0),State(-1,-1,0),State(-1,-1,0)] min = float('inf') while prev_state != [None, None, None]: prev_state = self.forward(a_list=a, b_list=b, prev_state=prev_state) return self.min if __name__ == '__main__': a = [1,4,1,1] b = [2,3,4,2] print( Solution().min_sum(a, b) )

动态规划

正在做这题，在线等答案

不太理解题意，个人想法，偏向贪心算法，想取最小和首先每个乘积都尽量小，而尽量小我看作是相邻两项的差越大就越想让这两项作乘法,先把俩个队列插入排序成一个队列，然后在新的有序队列中让依次取出头和尾各一项凑成一对，直到队列取完

暴力解决一切问题，比如数组有n个数字，将数组A内容移动到B中，第一次移动x次，x的取值范围为（0，n），第二次移动x取值范围为（0,n-x）。用递归，判定结束的条件为A全部移动过去，或者A中的某个元素已经移动到B的最后一位。我觉得这个题就是变态青蛙条的升级版本。