文章目录
-
- 原题题目
- 代码实现（首刷超时 TLE 50/85 dp）
- 代码实现（首刷看了点思路点拨后 二分自解）
原题题目
代码实现（首刷超时 TLE 50/85 dp）
class Solution {
public:int shipWithinDays(vector<int>& weights, int days) {
vector<vector<int>> dp(weights.size(),vector<int>(weights.size(),0));for(int i=0;i<weights.size();++i){
for(int j=i;j<weights.size();++j){
if(i == j) dp[i][j] = weights[j];else dp[i][j] = dp[i][j-1] + weights[j];}}vector<int> now_min(weights.size(),0),pre_min(now_min),tmp_zero(pre_min);vector<bool> now_visit(weights.size(),false),pre_visit(now_visit),tmp_false(now_visit);int ret = INT_MAX;for(int i=0;i<days;++i){
now_visit = tmp_false;now_min = tmp_zero;for(int start=i;start<weights.size();++start){
if(start && !pre_visit[start-1]) continue;for(int end=start;end<weights.size();++end){
now_visit[end] = true;if(!start){
now_min[end] = dp[start][end];continue;}if(!now_min[end]) now_min[end] = max(pre_min[start-1],dp[start][end]);else now_min[end] = min(now_min[end],max(pre_min[start-1],dp[start][end]));}}pre_visit = now_visit;pre_min = now_min;if(pre_visit.back()) ret = min(ret,pre_min.back());}return ret;}
};
代码实现（首刷看了点思路点拨后 二分自解）
class Solution {
public:int shipWithinDays(vector<int>& weights, int days) {
int left = 0,right = 0,sum = 0;for(const auto& num:weights){
left = max(left,num);right += num;}sum = right;while(left < right){
int mid = (left + right)/2;int tmpsum = 0;int day = 1,pos = 0;while(day <= days && pos < weights.size()){
if(tmpsum + weights[pos] > mid){
tmpsum = 0;++day;}elsetmpsum += weights[pos++];}if(day > days) left = mid+1;else right = mid;}return left;}
};