F1. Pictures with Kittens(easy version)[폭력]
F1. Pictures with Kittens (easy version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The only difference between easy and hard versions is the constraints.
Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of nn consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the ii-th picture has beauty aiai.
Vova wants to repost exactly x pictures in such a way that:
For example, if k=1 then Vova has to repost all the pictures in the news feed. If k=2 then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.
Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.
Input
The first line of the input contains three integers n,kn,k and xx (1≤k,x≤n≤200) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.
The second line of the input contains nn integers a1,a2,…,an(1≤ai≤109), where aiai is the beauty of the ii-th picture.
Output
Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.
Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.
Examples
input
5 2 3
5 1 3 10 1
output
18
input
6 1 5
10 30 30 70 10 10
output
-1
input
4 3 1
1 100 1 1
output
100
제목:
임의의 연속된 k개 수를 충족시키려면 최소한 하나의 선택이 있어야 합니다. x개의 최대치를 선택하십시오. 출력 -1이 존재하지 않으면 출력 최대치를 선택하십시오.
분석:
dp[i][k]는 전 i개 수 중 k개의 최대치를 선택하고, 이때 선택한 마지막 수는 a[i]입니다.
코드:
#include
#define ll long long
#define mod 1000000007
using namespace std;
ll a[210005];
ll dp[250][250];
int main()
{
ll i,j,k,l,n,x,tt;
scanf("%lld%lld%lld",&n,&k,&x);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
memset(dp,-mod,sizeof(dp));
dp[0][0]=0;
for(i=1;i<=n;i++)
{
tt=0;
tt=max(i-k,tt);
for(j=i-1;j>=tt;j--)
{
for(l=0;ln-k;i--)
maxn=max(maxn,dp[i][x]);
printf("%lld
",maxn);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[Wunder Fund Round 2016(Div 1 + Div 2 combined) B] [폭력 욕심] Guess the Permutation 전체 배열 a[i] [j]=min(p[i],ptime limit per test memory limit per test input standard input standard output Bob has a permutation of integers from 1 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.