[CodeForces 332B]Maximum Absurdity[DP]
주제 분석:
겹치지 않는 길이가 k인 두 개의 문자열을 찾아서 그것들의 합이 가장 크도록 해라.
문제 해결 방법:
첫 번째 생각은 이 점부터 길이가 k인 구간의 총화, 즉 getv[i]가 구간을 대표하는 [i, i+k-1]의 합을 처리하고 이걸 어떻게 쓸 수 있는지 생각하는 것이다.
그리고 처리할 수 있는 것을 발견한 후 getv[1]부터 매거하기 시작했고 dp[i]는 i부터 시작하여 가장 큰 구간과
그리고 getv[i]+dp[i+k]를 매번 업데이트하면 됩니다.
개인적인 느낌:
반짝반짝 빛나네 야==
구체적인 코드는 다음과 같습니다.
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#define ll long long
#define pr(x) cout << #x << " = " << (x) << '
';
using namespace std;
const int INF = 0x7f7f7f7f;
const int MAXN = 2e5 + 111;
ll a[MAXN], getv[MAXN];
struct P {
ll val, pos; //
}dp[MAXN];
int main()
{
int n, k;
while (cin >> n >> k) {
for (int i = 1; i <= n; ++i) cin >> a[i];
ll sum = 0;
for (int i = 1; i <= k; ++i) sum += a[i];
getv[1] = sum;
for (int i = k + 1; i <= n; ++i) {
sum += a[i] - a[i - k];
getv[i - k + 1] = sum;
}
dp[n - k + 1].val = getv[n - k + 1];
dp[n - k + 1].pos = n - k + 1;
for (int i = n - k; i > k; --i) {
if (getv[i] >= dp[i + 1].val) {
dp[i].val = getv[i];
dp[i].pos = i;
}
else {
dp[i].val = dp[i + 1].val;
dp[i].pos = dp[i + 1].pos;
}
}
int a = 0, b = 0;
ll mx = 0;
for (int i = k + 1; i <= n - k + 1; ++i) {
ll sum = getv[i - k] + dp[i].val;
if (sum > mx) {
mx = sum;
a = i - k;
b = dp[i].pos;
}
}
cout << a << ' ' << b << '
';
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.