第一題

題目

kanan和高音

思路

雙指針遍歷數組，更新左右端點并計算最大值

代碼

#include<iostream>
#include<vector>
using namespace std;int main()
{int n; cin >> n;vector<int> a(n);for(int i = 0; i < n; i++) cin >> a[i];int res = 1;for(int i = 0; i < n;){int j = i;while(j + 1 < n && a[j + 1] - a[j] <= 8) j++;res = max(res, j - i + 1);i = j + 1;}cout << res << endl;return 0;
}

第二題

題目

拜訪

思路

單源最短路： 額外利用一個cnt數組維護到當前位置的方法數

代碼

// https://www.nowcoder.com/practice/491828fc7d93459db450b344c2aaaeef?tpId=128&tqId=33770&ru=/exam/oj
#include<iostream>
#include<vector>
#include<queue>using namespace std;class Solution {int n, m;int x1, y1, x2, y2;int dist[11][11];int cnt[11][11];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};
public:/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** * @param CityMap int整型vector<vector<>> * @param n int整型 * @param m int整型 * @return int整型*/int countPath(vector<vector<int> >& CityMap, int _n, int _m) {// write code heren = _n, m = _m;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(CityMap[i][j] == 2){x1 = i, y1 = j; // 起點}if(CityMap[i][j] == 1){x2 = i, y2 = j; // 終點}}}return bfs(CityMap);}int bfs(vector<vector<int> >& CityMap){memset(dist, -1, sizeof(dist));queue<pair<int, int>> q;q.push({x1, y1});dist[x1][y1] = 0;cnt[x1][y1] = 1;while(q.size()){auto [a, b] = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i];int y = b + dy[i];if(x >= 0 && x < n && y >= 0 && y < m && CityMap[x][y] != -1){if(dist[x][y] == -1){dist[x][y] = dist[a][b] + 1;cnt[x][y] = cnt[a][b];q.push({x, y});}else if(dist[x][y] == dist[a][b] + 1){cnt[x][y] = (cnt[x][y] + cnt[a][b]);}}}}return cnt[x2][y2];}
};

第三題

題目

買賣股票的最好時機(四)

思路

動態規劃

• 狀態表示：

  • f[i][j]第i天結束后操作了j次，手里有股票；
  • g[i][j]第i天結束后操作了j次，手里沒有股票；

• 狀態轉移方程：

  • 對于f[i][j]：
    • 前一天手里有股票，交易了j次，第i天什么也不干，此時f[i][j] = f[i - 1][j]
    • 前一天手里沒股票，交易了j次，第i天買入股票，此時f[i][j] = g[i - 1][j] - price[i]
  • 對于g[i][j]：
    • 前一天手里有股票，交易了j - 1次，第i天賣出股票，此時g[i][j] = f[i - 1][j - 1] + price[i]
    • 前一天手里沒股票，交易了j次，第i天什么也不干，此時g[i][j] = g[i - 1][j]

• 初始化：由于需要?到i = 0 時的狀態，因此我們初始化第??即可

  • 第0天時，買?過?次， f[0][0] = - prices[0]

• 填表順序：從上往下填每??，每??從左往右，兩個表?起填

• 返回值：返回處于賣出狀態的最?值，但是我們也不知道是交易了?次，因此返回g 表最后??的最?值

代碼

	#include <cstring>
#include <iostream>
using namespace std;const int N = 1010, M = 110;
int n, k, p[N];
int f[N][M], g[N][M];int main() 
{cin >> n >> k;for(int i = 0; i < n; i++) cin >> p[i];memset(f, -0x3f3f3f3f, sizeof f);memset(g, -0x3f3f3f3f, sizeof g);k = min(k, n / 2);f[0][0] = -p[0];g[0][0] = 0;for(int i = 1; i < n; i++){for(int j = 0; j <= k; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]);g[i][j] = g[i - 1][j];if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]);}}int ret = 0;for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);cout << ret << endl;return 0;
}
// 64 位輸出請用 printf("%lld")