1 dp: 首先搞明白动态规划的单元,注意,不仅仅是说增加一个元素,对分割造成了什么影响,而且还要考虑,不通的分割数目,本题目是分割,那么一定是分割数目以及分割对象带来的变化为dp的状态迁移, dp[i][j] means: res of: nums[:i] to be splited in j’s segments, dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1},所以
classSolution { public: intsplitArray(vector<int>& nums, int m){ int n = nums.size(); vector<int> preSum = { 0 }; for(int i = 0; i < n; ++i) { preSum.push_back(preSum.back() + nums[i]); } // // dp[i][j] means: res of: nums[:i] to be splited in j's segments // // dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1} // vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX)); // dp[1][1] = nums[0]; // for(int i = 1; i <= n; ++i) { // for(int j = 1; j <= min(m, i); ++j) { // if(j == 1) { // dp[i][1] = preSum[i] - preSum[0]; // continue; // } // int tmpMaxMin = 0; // for(int k = j - 1; k < i; ++k) { // tmpMaxMin = max(dp[k][j-1], preSum[i] - preSum[k]); // dp[i][j] = min(dp[i][j], tmpMaxMin); // } // } // } // return dp[n][m]; // binsearch x as the min max res int st = *max_element(nums.begin(), nums.end()); int ed = preSum[n]; int x = -1;
bool lastCheck = false; while(st < ed) { x = (st + ed) >> 1; lastCheck = xIsLarge(x, nums, m); if(lastCheck) { ed = x; // when ed - st = 1, (st + ed) >> 1 == st } else { st = x + 1; } } // at last, st == ed return st; }
boolxIsLarge(int x, vector<int>& nums, int m){ int cnt = 1; int curSum = 0; for(int i = 0; i < nums.size(); ++i) { if(curSum + nums[i] > x) { ++cnt; curSum = nums[i]; } else { curSum += nums[i]; } } // cout << ">> x/cnt is" << x << "/" << cnt << endl; return cnt <= m; } };
classSolution { public: boolcanCross(vector<int>& stones){ int n = stones.size(); // jump to i, and last jump dis vector<vector<bool>> jump(n , vector<bool>(n, false)); jump[0][0] = true;
// the i th jump len <= i for(int i = 1; i < n; ++i) { if(stones[i] - stones[i - 1] > i) { returnfalse; } }
// dp, from j jump to i bool res = false; for(int i = 1; i < n; ++i) { for(int j = 0; j < i; ++j) { int k = stones[i] - stones[j]; // cout << j << " -> " << i << " 's dis: " << k << endl; if(k > j + 1) { continue; } // cout << jump[j].size() << " / " << k + 1 << " jump[j][k] || jump[j][k-1] || jump[j][k+1] " << jump[j][k] << jump[j][k-1] << jump[j][k+1] << endl; jump[i][k] = jump[j][k] || jump[j][k-1] || jump[j][k+1]; if(i == n - 1 && jump[i][k]) { res = true; } } } return res; } };
// case1: cut the same ball if(tarBallStr == lastTarBallStr) { continue; }
// use this char, find put pos for(int i = 0; i <= board.size(); ++i) { // case2: only insert at the start of str with same chars if(i > 0 && board[i - 1] == hand[k]) { continue; }
// case3: only put when cur is equal current || when cur is not equal to two continuous same chars if(i < board.size() && board[i] == hand[k] || \ i > 0 && board[i] == board[i-1] && hand[k] != board[i-1]) { string tmpBoard1 = board; tmpBoard1.insert(i, tarBallStr); // reduce repeat balls reduceRepeat(tmpBoard1);
// put to tarBall left and right int lRes = bfs(tmpBoard1, nextHand);
int bigInt = 1000000007; intcheckRecord(int n){ if(n <= 2) { return n == 1 ? 3 : 8; } // we can use A to interrupt the LLL, so we calculate A after only PL // // n's day without 'A' // vector<vector<long long>> dp(n + 1, vector<long long>(3, 0)); // // dp[i][j], j means end with n's L // dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0;
// for(int i = 2; i <= n; ++i) { // // end with p // dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]; // // ent with l // dp[i][1] = (dp[i - 1][0]) % bigInt;
// // when there is a A: // long long res = 0; // res += ((dp[n][0] + dp[n][1]) % bigInt + dp[n][2]) % bigInt; // res += (((dp[n-1][0] + dp[n-1][1]) % bigInt + dp[n-1][2]) % bigInt * n) % bigInt;
// n's day without 'A' vector<vector<vector<longlong>>> dp(n + 1, vector<vector<longlong>>(2, vector<longlong>(3, 0))); // dp[i][j], j means end with n's L dp[0][0][0] = 1;
for(int i = 1; i <= n; ++i) { // end with p for(int j = 0; j < 2; ++j) { for(int k = 0; k <= 2; ++k) { dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % bigInt; } }
// end with a for(int k = 0; k <= 2; ++k) { dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k]) % bigInt; } // ent with l for(int j = 0; j < 2; ++j) { for(int k = 1; k <= 2; ++k) { dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k-1]) % bigInt; } } }
int res = 0;
for(int j = 0; j < 2; ++j) { for(int k = 0; k < 3; ++k) { res = (res + dp[n][j][k]) % bigInt; } }
// assume the biggest bit starts with 0 int res = dp[lastOneBitIdx][0] + dp[lastOneBitIdx][1]; // cout << "assume biggest bit = 0's res : " << res << endl;