3311

TheGiao
INnoVation
zombotany
knighz
fighting_HZ

zyn酱

class Solution {
private:
vector<int> a;
int n;
public:
Solution(vector<int>& a) {
this->a = a;
this->n = a.size();
}

/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return a;
}

/** Returns a random shuffling of the array. */
vector<int> shuffle() {
auto b = a;
for (int i = 0; i < n; i++) {
swap(b[i], b[i + rand() % (n - i)]);
}
return b;
}
};

/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
*/


#include <iostream>
using namespace std;

const int N = 10000;
int a[N], f[N];
int n;

// 状态表示：f[i] 表示所有以 a[i] 为结尾的上升子序列的最大长度
// 状态计算：f[i] = max(f[0], f[1], ... , f[i - 1], f[i])

int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];

for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}
}

int res = 0;
for (int i = 1; i <= n; i++) {
res = max(res, f[i]);
}

cout << res << endl;
return 0;
}


#include <iostream>

using namespace std;
const int N = 510;
int a[N][N];

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> a[i][j];
}
}

for (int j = n - 1; j >= 1; j--) {
for (int i = n - 1; i >= j; i--) {
a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
}
}

cout << a[1][1] << endl;
return 0;
}


#include <iostream>

using namespace std;

const int N = 110;
int v[N][N], w[N][N], s[N], f[N];

int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
for (int j = 1; j <= s[i]; j++) cin >> v[i][j] >> w[i][j];
}

for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 1; k <= s[i]; k++) {
if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
cout << f[m] << endl;

return 0;
}


### 代码

class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *h) {
if (!h || !h->next) return nullptr;
auto p = h->next->next, q = h->next;
while (p->next->next && p != q) p = p->next->next, q = q->next;
if (!p->next->next) return nullptr;
p = h;
while (p != q) p = p->next, q = q->next;
return p;
}
};


## 代码

### 原始做法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[N][K][2];

int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i];

memset(f, -0x3f, sizeof f);
for (int i = 0; i <= n; i++) f[i][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
f[i][j][0] = max(f[i - 1][j][1] + w[i], f[i - 1][j][0]);
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
}
}

int res = 0;
for (int i = 0; i <= k; i++) {
res = max(res, f[n][i][0]);
}
cout << res << endl;

return 0;
}


### 滚动数组优化

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[K][2];

int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i];

memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
f[j][0] = max(f[j][1] + w[i], f[j][0]);
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);
}
}

int res = 0;
for (int i = 0; i <= k; i++) {
res = max(res, f[i][0]);
}
cout << res << endl;

return 0;
}


#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int w[N], f[N];

int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
f[1] = w[1];
for (int i = 2; i <= n; i++) {
f[i] = max(f[i - 2] + w[i], f[i - 1]);
}
cout << f[n] << endl;;
}
return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int w, f[3];

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) ;

f[0] = f[1] = -0x3f3f3f, f[2] = 0;
for (int i = 1; i <= n; i++) {
cin >> w;
int a = max(f[0], f[2] - w);
int b = f[0] + w;
int c = max(f[1], f[2]);
f[0] = a;
f[1] = b;
f[2] = c;
}

cout << max(f[1], f[2]) << endl;

return 0;
}


## 代码

### 原始做法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int w[N], f[N][3];

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];

f[0][0] = f[0][1] = -0x3f3f3f, f[0][2] = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
f[i][1] = f[i - 1][0] + w[i];
f[i][2] = max(f[i - 1][1], f[i - 1][2]);
}

cout << max(f[n][1], f[n][2]) << endl;

return 0;
}


### 滚动变量优化空间

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int w, f[3];

int main() {
int n;
cin >> n;

f[0] = f[1] = -0x3f3f3f, f[2] = 0;
for (int i = 1; i <= n; i++) {
cin >> w;
int a = max(f[0], f[2] - w);
int b = f[0] + w;
int c = max(f[1], f[2]);
f[0] = a;
f[1] = b;
f[2] = c;
}

cout << max(f[1], f[2]) << endl;

return 0;
}


## 代码

### 原始做法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[N][K][2];

int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i];

memset(f, -0x3f, sizeof f);
for (int i = 0; i <= n; i++) f[i][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
f[i][j][0] = max(f[i - 1][j][1] + w[i], f[i - 1][j][0]);
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
}
}

int res = 0;
for (int i = 0; i <= k; i++) {
res = max(res, f[n][i][0]);
}
cout << res << endl;

return 0;
}


### 滚动数组优化

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[K][2];

int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i];

memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
f[j][0] = max(f[j][1] + w[i], f[j][0]);
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);
}
}

int res = 0;
for (int i = 0; i <= k; i++) {
res = max(res, f[i][0]);
}
cout << res << endl;

return 0;
}