로곡 P2034 선택 숫자

8805 단어 dp 낙곡

제목 설명은 한 줄에 n개의 비음정수 a[1]...a[n]를 정한다.현재 너는 그 중 몇 개의 수를 선택할 수 있지만, k개의 연속적인 숫자를 초과해서는 안 된다.너의 임무는 선택한 숫자와 가장 큰 숫자를 만드는 것이다.
입력 형식 첫 번째 행의 정수 n, k
다음 n행은 각 행의 정수로 a[i]를 나타냅니다.
출력 형식 출력 값은 답을 표시합니다.
작은 dp 하나. 저희가 f[i]를 설정해서 i의 최우수치를 뽑지 않으려고 60점 폭력을 썼는데 산소를 한 모금 들이마셨어요.

#include 
#include 
#include 
#define int long long 
using namespace std;
int n,k;
int a[100005];
int sum[100005];
int f[100005];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
main(){
	n=read();k=read(); 
	for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];
	int q=0;
	for(int i=1;i<=n+1;i++)
    for(int j=max(q,i-k-1);j<i;j++)
    f[i]=max(f[i],f[j]+sum[i-1]-sum[j]);
    printf("%lld",f[n+1]);
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

【경쟁 프로 전형적인 90문】008의 해설(python)

의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다