Решение задачи "Юра и работа" с Codeforces

Без пояснения   Просмотров: 13

Совсем недавно вышел новый ITone 6, и Юра очень захотел себе его купить. К сожалению, денег у него не хватало, поэтому Юра устроился работать программистом. На работе Юра столкнулся со следующей задачей:

Задана последовательность из n чисел p 1, p 2, ..., p n. Нужно выбрать k пар целых чисел:

[l 1, r 1], [l 2, r 2], ..., [l k, r k] (1 ≤ l 1 ≤ r 1 < l 2 ≤ r 2 < ... < l k ≤ r k ≤ n; r i - l i + 1 = m), 
так чтобы сумма была как можно больше. Помогите Юре справиться с этим заданием.

Код 

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4;
long long dp[5003][5003];
int main(){
	int n , m ,k;
	cin >> n >> m >> k;
	long long p[n];
	for(int i = 1;i <= n; i++){
		cin >> p[i];
		p[i] += p[i - 1];
	}
	for(int i = 1; i <= k; i++){
		for(int j = m; j <= n; j++){
			dp[i][j] = max(dp[i][j - 1] , dp[i - 1][j - m] + p[j] - p[j - m]);
		}
	}
	cout << dp[k][n];	
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться