/* 贪心 负数一定不取 枚举最高位是1 且答案取为0的 位置， 更新答案。 */ #include<iostream> #include<cstdio> #include<cstring> #define ll long long #define N 100010 using namespace std; int n; ll a[N],ans,sum[N]; char s[N]; ll read() { ll x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main() { freopen("maximum.in","r",stdin); freopen("maximum.out","w",stdout); scanf("%d",&n); for(int i=1; i<=n; i++) { a[i]=read(); sum[i]=sum[i-1]; if(a[i]>0)sum[i]=sum[i-1]+a[i]; } scanf("%s",s+1); ll c=0; for(int i=n; i>=1; i--) if(s[i]=='1') { ans=max(ans,c+sum[i-1]); c+=max(a[i],0LL); } ans=max(ans,c); printf("%I64d\n",ans); return 0; }
/* 15暴力 */ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1010 using namespace std; int n,k; int l,r,mid; int num[N],tmp[N]; int ans; int minn(int a,int b,int i) { if(a<b) return tmp[i-1]; else return tmp[i-1]+mid; } bool check() { int sum=0; for(int i=1; i<=n; i++) tmp[i]=num[i]; for(int i=2; i<=n; i++) if(abs(tmp[i]-tmp[i-1])>mid) { if(tmp[i+1]>tmp[i]) tmp[i]=max(tmp[i],tmp[i-1]+mid); else tmp[i]=minn(abs(tmp[i-1]-tmp[i+1]),tmp[i-1]+mid-tmp[i+1],i); sum++; } if(sum>k) return false; else return true; } int main() { scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) scanf("%d",&num[i]); l=0; r=1000000000; while(l<=r) { mid=(l+r)/2; if(check()) ans=mid,r=mid-1; else l=mid+1; } printf("%d",ans); }
不会分块
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <ctime> using namespace std; const int maxn = 200000; const int len = 400; int n, A, B,m; int a[maxn],b[maxn],l[maxn],r[maxn],lb[maxn],tot; int answer[300][300]; int rt[300][maxn], lt[300][maxn],d[maxn]; //int root[maxn*len], ll[maxn*len], rr[maxn*len],data[maxn*len]; int find(int x) { for (int l = 0, r = m; l < r;) { int mid = (l + r) / 2; if (b[mid] == x) return mid; if (b[mid]>x) r = mid; else l = mid + 1; } return -1; } /*int build(int l, int r) { if (l == r) { tot++; ll[tot] = rr[tot] = 0; data[tot] = d[l]; return tot; } tot++; int tmp = tot; ll[tmp] = build(l, (l + r) / 2); rr[tmp] = build((l + r) / 2 + 1, r); data[tmp] = min(data[ll[tmp]], data[rr[tmp]]); return tmp; } int change(int i, int l, int r,int x) { if (l == x && r == x) { tot++; ll[tot] = rr[tot] = 0; data[tot] = n + 1; return tot; } tot++; int tmp = tot; ll[tot] = ll[i]; rr[tot] = rr[i]; if (l <= x && x <= (l + r) / 2) ll[tmp] = change(ll[i], l, (l + r) / 2, x); else rr[tmp] = change(rr[i], (l + r) / 2 + 1, r, x); data[tmp] = min(data[ll[tmp]], data[rr[tmp]]); return tmp; } int check(int i, int l, int r, int x, int &ans) { if (l > x) return 0; if (1 <= l && r <= x) { ans = min(ans, data[i]); return 0; } check(ll[i], l, (l + r) / 2, x, ans); check(rr[i], (l + r) / 2 + 1, r, x, ans); return 0; }*/ int main() { double ti = clock(); freopen("sequence.in", "r", stdin); freopen("sequence.out", "w", stdout); scanf("%d%d%d", &n, &A, &B); a[0] = 0; for (int i = 1; i <= n; i++) { char c; for (scanf(" %c", &c); c != 'A' && c != 'B'; scanf(" %c", &c)); if (c == 'A') a[i] = a[i - 1] + B; else a[i] = a[i - 1] - A; } for (int i = 0; i <= n; i++) b[i] = a[i]; sort(b, b + n + 1); m = unique(b, b + n + 1) - b; for (int i = 0; i <= n; i++) { a[i] = find(a[i]); if (a[i] == -1) { printf("???\n"); return 0; } } n++; int k = n / len; for (int i = 0; i <= k; i++) { int ans = 0; tot++; for (int j = i*len; j < n; j++) { if (j%len == 0) { answer[i][j / len] = ans; } if (lb[a[j]] != tot) { lb[a[j]] = tot; l[a[j]] = j; } ans = max(ans, j - l[a[j]]); } } for (int i = 0; i < n; i++) r[i] = -1; for (int i = 0; i < n; i++) { r[a[i]] = i; if (i%len == len - 1) { int tmp = i / len; for (int j = 0; j < n; j++) rt[tmp][j] = r[j]; } } for (int i = 0; i < n; i++) l[i] = -1; for (int i = n - 1; i >= 0; i--) { l[a[i]] = i; if (i%len == 0) { int tmp = i / len; for (int j = 0; j < n; j++) lt[tmp][j] = l[j]; } } int q; scanf("%d", &q); int ans = 0; for (; q; q--) { int L, R; scanf("%d%d", &L, &R); L--; int kl = L / len, kr = R / len; ans = 0; if (kl == kr) { tot++; for (int i = L; i <= R; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; } ans = max(ans, i - l[a[i]]); } } else { ans = answer[kl + 1][kr]; tot++; int tmp = min(n, (kl + 1)*len); for (int i = L; i < tmp; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; ans = max(ans, rt[kr - 1][a[i]] - i); } } tmp = min(R + 1, n); for (int i = kr*len; i < tmp; i++) { if (lb[a[i]] != tot) { if (lt[kl + 1][a[i]] != -1) ans = max(ans, i - lt[kl + 1][a[i]]); } else ans = max(ans, i - l[a[i]]); } } printf("%d\n", ans); } /*int q; for (scanf("%d", &q); q; q--) { // if (q % 5000 == 0) cerr << q << endl; int L, R; tot++; scanf("%d%d", &L, &R); int ans = 0; for (int i = L - 1; i <= R; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; } ans = max(ans, i - l[a[i]]); } printf("%d\n", ans); }*/ /*for (int i = 0; i <= n; i++) { if (lb[a[i]] == 0) { lb[a[i]] = 1; l[a[i]] = i; d[i] = n + 1; } else { r[l[a[i]]] = i; d[i] = i - l[a[i]]; l[a[i]] = i; } } root[0] = build(1, n); for (int i = 1; i <= n; i++) { if (r[i-1] != 0) root[i] = change(root[i - 1], 1, n, r[i-1]); else root[i] = root[i - 1]; } int q; for (scanf("%d", &q); q; q--) { int L, R; scanf("%d%d", &L, &R); L--; int ans = n + 1; check(root[L], 1, n, R, ans); if (ans == n + 1) printf("-1\n"); else printf("%d\n", ans); }*/ /* int q; int tans = 0; for (scanf("%d", &q); q; q--) { int L, R; scanf("%d%d", &L, &R); L--; tot++; int ans = n + 1; for (int i = L; i <= R; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; } else { ans = min(ans, i - l[a[i]]); l[a[i]] = i; } } if (ans == n + 1) printf("-1\n"); else { printf("%d\n", ans); tans = max(tans, ans); } } cerr << clock()-ti << " "<<tans<<" "<<A<<" "<<B<<endl;*/ return 0; }