2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5+10;
int w[N], s[N], min_v[N];
deque<int> q; // fornt in, tail out
// f[i] is the maximum sum for sequeces that has a size smaller than m and ending at w[i].
// f[i] = max(s[i] - s[i-1], s[i] - s[i-2], ..., s[i] - s[i-m])
// f[i] could
int main (){
int n, m;
cin >> n >> m;
// cout << "0 ";
for (int i=1; i<=n; i++) {
cin >> w[i];
s[i] = s[i-1] + w[i];
// cout << s[i] << " ";
}
// cout << endl;
for (int i=0; i<=n; i++) {
while(!q.empty() && s[i] < s[q.front()]) q.pop_front();
q.push_front(i);
if (!q.empty() && (q.front() - q.back() + 1) > m) q.pop_back();
min_v[i] = s[q.back()];
// cout << min_v[i] << " ";
}
// cout << endl;
int res = INT_MIN;
for (int i=1; i<=n; i++) {
res = max(res, s[i] - min_v[i-1]);
}
cout << res;
}


2个月前
#include <bits/stdc++.h>

using namespace std;
const int N = 50;
int f[N][N], g[N][N], w[N];
int n;
void preorder(int l, int r) {
int root = g[l][r];
cout << g[l][r] << " ";
if (root > l) {
preorder(l, root-1);
}
if (root < r) {
preorder(root+1, r);
}
}

void init() {
memset(f, -0x3f, sizeof f);
for (int i=1; i<=n; i++) {
f[i][i] = w[i];
g[i][i] = i;
}
}
int main() {
cin >> n;
for(int i=1; i<=n; i++) cin >> w[i];
init();
for(int len=2; len <= n; len++) {
for (int left=1; left + len - 1 <= n; left ++) {
int right = left + len - 1;
int res = INT_MIN;
int res_k = -1;
for (int k=left; k<=right; k++) {
int left_v = (left > k-1) ? 1: f[left][k-1];
int right_v = (k+1 > right) ? 1 : f[k+1][right];
int tmp = left_v * right_v + w[k];
if (tmp > res) {
res = tmp;
res_k = k;
}
}
f[left][right] = res;
g[left][right] = res_k;
}
}
cout << f[1][n] << endl;
preorder(1, n);
}


2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 505;
int w[N], s[N];
int f[N][N], g[N][N]; // f[i, j]
int main(){
int n;
cin >> n;
for (int i=1; i<=n; i++) {
cin >> w[i];
w[i+n] = w[i];
}
memset(f, -0x3f, sizeof f);
memset(g, 0x3f, sizeof g);
for (int i=1; i<=2*n; i++) {
f[i][i] = 0;
g[i][i] = 0;
s[i] = s[i-1] + w[i];
}
for (int len=2; len <= n; len++){
for (int i=1; (i+len-1)<=2*n; i++) {
int j=i+len-1;
int res = INT_MAX;
int res2 = INT_MIN;
for (int k=i; k<j; k++) {
res = min(res, f[i][k] + f[k+1][j] + (s[j] - s[i-1]));
res2 = max(res2, g[i][k] + g[k+1][j] + (s[j] - s[i-1]));
}
f[i][j] = res;
g[i][j] = res2;
}
}
int ans = INT_MAX;
int ans2 = INT_MIN;
for (int i=1; i<=n; i++) {
ans = min(ans, f[i][i+n-1]);
ans2 = max(ans2, g[i][i+n-1]);
}
cout << ans << endl;
cout << ans2 << endl;
}


2个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int f[N][3];
int w[N];
int main () {
int n;
cin >> n;
for (int i=1; i<=n; ++i) cin >> w[i];
memset(f, -0x3f, sizeof f);
f[1][0] = 0;
f[1][1] = -w[1];
for (int i=2; i<=n; i++) {
f[i][0] = f[i-1][0];
f[i][1] = f[i-1][1];
f[i][0] = max(f[i][0], f[i-1][2]);
f[i][1] = max(f[i-1][0] - w[i], f[i][1]);
f[i][2] = f[i-1][1] + w[i];
}
cout << max(f[n][0], f[n][2]);
}


2个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int K = 110;
int f[N][2][K];
int w[N];
// f i j 走了i步，进行了j次买卖，目前是0/1仓位的最大收益
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=1; i<=n; i++) {
f[i][0][0] = 0;
}
f[1][0][0] = 0;
f[1][1][1] = -w[1];
for (int i=2; i<=n; i++) {
for (int j=1; j <= k; j++) {
f[i][1][j] = max(f[i-1][1][j], f[i-1][0][j-1] - w[i]);
f[i][0][j] = max(f[i-1][0][j], f[i-1][1][j] + w[i]);
}
}
int res = 0;
for (int i=0; i<=k; i++) {
res = max(res, f[n][0][i]);
}
cout << res << endl;
}


2个月前
#include <bits/stdc++.h>
using namespace std;

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

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


2个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
int f[N][2];
bool st[N];
vector<vector<int>> edges;
void add(int a, int b) {

edges[a].push_back(b);
}
void dfs(int u) {
if (edges[u].empty()) {
f[u][0] = 0;
f[u][1] = 1;
return;
}
f[u][1] = 1;
for (auto i: edges[u]) {
dfs(i);
f[u][1] += min(f[i][1], f[i][0]);
f[u][0] += f[i][1];
}
}
int main() {
int n;
while(cin >> n) {
memset(f, 0, sizeof f);
memset(st, 0, sizeof st);
edges.clear();
edges = vector<vector<int>>(n, vector<int>());
int a, b;
for (int i=0; i<n;i++) {
scanf("%d:(%d)", &a, &b);
for (int i=0; i<b; i++) {
int c;
cin >> c;
st[c] = true;
}
}
int root=0;
while(root < n && st[root]) root ++;
dfs(root);
cout << min(f[root][0], f[root][1]) << endl;
}
}


3个月前
#include<bits/stdc++.h>
using namespace std;
int dp[1010];
int w[1010];
int main() {
int n;
cin >> n;
int res=0;
for (int i=0; i<n; i++) cin >> w[i];
for (int i=0; i<n; i++) {
int __max=0;
dp[i] = w[i];
for (int j=0;j<i; j++) {
if (w[i] > w[j]) {
__max = max(__max, dp[j]);
}
}
dp[i] += __max;
res = max(dp[i], res);
}
cout << res;
}


3个月前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
vector<PII> f;
const int N = 6e3;
int dp[N];

int main() {
int n;
cin >> n;
for (int i=0; i<n;i ++) {
int a, b;
cin >> a >> b;
f.push_back({a, b});
}
sort(f.begin(), f.end());
int res = 0;
for (int i=0; i<n; i++) {
dp[i] = 1;
for (int j=0; j<i; j++) {
if (f[j].second < f[i].second) dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}

cout << res;
}


3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3;
int w[N], f[N], f2[N];
int main() {
memset(w, 0, sizeof w);
int n;
int res=0;
cin >> n;
for (int i=1; i <= n; i++) {
cin >> w[i];
}

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

for (int i=n; i>0; --i) {
f2[i] = 1;
for (int j=n; j>i; --j) {
if (w[j] < w[i]) f2[i] = max(f2[i], f2[j] + 1);
}
}

for (int i=1; i<=n; i++) res = max(res, f[i] + f2[i] - 1);
cout << n-res;
}