BOJ 208-宝石拾い

タイムアウトメモリ制限正解の発行正解正解正解正解正解率2秒128 MB 125240233.275%
質問する
花英は古代遺跡の調査で宝石を発見した.遺跡にはN(1≦N≦100000)粒の宝石が並んでいます.それぞれの宝石の価値が異なる可能性があるので、花影はできるだけ多くの宝石を持って、利益を得ることができます.この場合、以下の3つの条件を満たさなければならない.

宝石は1番からN番まで順番に並べられ、花英は1番の宝石が置かれているところからN番の宝石が置かれているところまで順番に移動します.しかし宝石の間には罠が設けられており、宝石を拾う途中でUターンすることはできない.そのため、花英は宝石を置く位置で宝石を拾ったり、通りかかったりして、次の宝石の位置に移動します.

遺跡には罠だけでなく、警報装置も設置されている.この装置は、遺跡に入った人が宝石を拾う際に侵入者と見なし、侵入者が宝石を拾うのを止める際に遺跡を押し倒すように設計されている.しかし、この警報装置は数え切れないほどあり、M(1≦M≦N)個以上の宝石を拾い続けると混同し、遺跡が少し遅れて倒壊する.そのため、いったん宝石を拾い始めると、位置上の宝石も含めてM個以上の宝石を拾い続け、いったん宝石を拾うのをやめると、他の宝石を拾う暇もなく、急いで遺跡を離れなければならない.

宝石は重いので、宝石を拾う以上、できるだけ高い宝石で拾うようにします.つまり、拾った宝石の価値を総和して最大化する.しかし、いくつかの宝石の価値は負の数かもしれません.

ジュエリーの数が多いため、華英はパソコンでこの問題を解決することにした.宝石に関する情報を得た場合は、上記の条件を満たし、移動時に得られる価値の総和の最値を求めるプログラムを作成します.
入力
第1行は2つの整数N,Mを与える.次のN行は各宝石に順次価値を与える.各宝石価値の節値は2000以下の整数である.
しゅつりょく
最初の行は、値の合計の最大値を出力します.
に近づく
これは少なくともM個以上連続する最大和を探す問題である.
まず,インデックスごとにM個の連続和を求める.
次に巡回中にi-1テーブル+arr[i]とsum[i]の値から大きな値をとるとよい.
答えはdptabelの最低価格です.
に答える
sum配列でM個の連続和を求めた.
次に,dp配列に擬似点火式を用いる.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, M, ans = 0, arr[100001], dp[100001], sum[100001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN2(N, M);
	FUP(i, 1, N)
	{
		CIN(arr[i]);
		sum[i] = sum[i - 1] + arr[i];
		if (i > M) sum[i] -= arr[i - M];
	}
	dp[M] = sum[M];
	ans = max(ans, dp[M]);
	FUP(i, M + 1, N)
	{
		dp[i] = max(dp[i - 1] + arr[i], sum[i]);
		ans = max(dp[i], ans);
	}
	COUT(ans);

	return 0;
}