제목 배경

전송문: [SWTR-03] Golden Sword

작은 E {mathrm {E} E는 불행하게도 전투에서 그의 김보검을 잃었다.

제목 설명

금보검을 만들려면 nn종의 원료가 필요하다. 번호는 11에서 nn, 번호는ii의 원료의 견고치는 ai{a i}ai이다.연금은 원료를 넣는 순서를 중시하기 때문에 작은 E {\mathrm {E} E는 반드시 1부터 n까지의 순서대로 이 원료를 연금 솥에 넣어야 한다.
하지만 연금 솥의 용량은 한계가 있어 최대 w개의 원료만 수용할 수 있다.
다행히 하나의 원료를 넣기 전에 작은 E {\mathrm {E} E는 그 중에서 일부 원료를 꺼낼 수 있고 수량은 s개를 초과할 수 없다.
제 i {i} i종의 원료를 넣을 때 증가하는 내구도: 솥 안의 원료 총수\a i {*a i}\ai로 보검의 내구도가 모든 원료의 내구도를 합친다.
작은 E {\mathrm {E} E는 당연히 그의 보검의 내구도를 가능한 한 크게 하려고 한다. 그러면 그는 그것을 가지고 더 많은 전투를 할 수 있고, 내구도의 최대치를 구할 수 있다.
주: 여기'제i종 원료를 넣었을 때 솥 안의 원료 총수는 솥에 넣고 있는 원료를 포함하고 상세한 정보는 샘플을 보십시오.

입력 형식

첫 번째 줄, 세 개의 정수 n, w, s. 두 번째 줄, n개의 정수 a 1, a 2,..., a n {a 1, a 2,\dots, a n} a1, a2,..., an.

출력 형식

한 줄의 정수로 내구도의 최대치를 나타낸다.
입력 출력 예 입력 #1 5 3 1 3 2 4 5 출력 #1 40 입력 #2 5 3 1 - 3 - 2 4 5 출력 #2 21 입력 #3 7 4 2 - 5 3 - 1 - 4 7 - 6 5 출력 #3 17 입력 #4 5 3 1 - 3 - 2 - 4 - 5 출력 #4 - 15
설명/프롬프트는 100% 데이터에 대해 1≤s≤w≤n≤5500, 0≤a i≤1 0 9 {1\leq s\leq w\leq n\leq 5500, 0\leq | a i |\leq 10^9} 1≤s≤w≤ n≤5500, 0≤\ai≤109(시한 500m s {500ms}) 공간에 대해 256m B {256m}

아이디어 및 코드

이 문제는 DP 베테랑에게는 매우 간단하지만 나 같은 DP 베테랑에게는 더할 나위 없이 어렵다.다음은 사고방식을 말해 보시오.우리는 먼저 DP의 문제풀이 방식을 통해 사고를 도울 수 있다. 첫째, 상태를 찾는다. 본 문제는 2차원 상태 폭력 DP로 문제를 푸는 것이다.제목의 뜻에 따라 f[i][j]{f[i][j]}f[i][j][j]로 제i{i}i개 원료를 냄비에 넣고 j{j}j개 원료를 넣을 때의 내구도의 최대치를 쉽게 알 수 있다.둘째, 기본 처리. 이 문제의 ai {a i}ai는 마이너스일 수 있기 때문에 최대치를 요구하려면 모든 상태량의 초기값을 마이너스로 해야 한다. 또한DP는 확정된 원시 상태량을 필요로 하기 때문에 우리는 f[0] [0] {f[0]} f[0]} f[0]]의 값을 0(분명)으로 부여해야 한다.마지막으로 우리가 요구한 답은 ans {ans}ans가 바로 m a x(f[n] [j])(1=#include #define N 6000 #define ll long long using namespace std; ll n,m,s; ll a[N],f[N][N],ans=-1e17+7; int main() { scanf("%lld%lld%lld",&n,&m,&s); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) f[i][j]=-1e17+7; f[0][0]=0; for(int i=1;i<=n;i++) for(int j=m;j>0;j--) { for(int k=min(m,s+j-1);k>=j-1;k--) f[i][j]=max(f[i][j],f[i-1][k]+j*a[i]); } for(int i=0;i<=m;i++) ans=max(ans,f[n][i]); cout<<ans<<endl; return 0; }

그리고 QAQ???

이 알고리즘의 복잡도는 O(m n2) {O(m*n^2)} O(m n2)이기 때문에 T.가 될 것이다. 이때 나는 화가 났다. 나는 TM가 두 시간 동안 이 사내의 눈에 1분이면 자르는 간단한 DP 문제를 만드는데 걸렸어?!!본론으로 돌아가 어려움에 부딪히면 우리는 포기할 수 없다. 미소 지으며 그것에 직면해야 한다.가능한 최적화된 모든 방법을 찾은 후에 저는 다음과 같은 것을 발견했습니다. f[i] [j] = m a x (f[i] [j], f[i: 1] [k] [k] + j는 [i]) (j: [i] [i]] [j] = [j] = [i]) (j] = m i n (m, j+ s: 1) {f[i] [j] [max (f[i] f[i] [i] f[i-1] [i] [i] [i] [i] (k] + j* + j* a [i]) (j: j++ [i]) (j: j [i]) min [j [j++++++ j [i]] (j < = < i]]) (j < = < [j], f[i-4-1][k]+j[i])(j-1<=k<=min(m, j+s-1)) 중 j[i] {j*a[i]} j a[i]는 사실 정해진 값이고,그래서 우리는 그것을 f[i] [j] [j] = m a x(f [ii 1] [k]] + j e[i] a [i] (j 1 <=k = m i n (m, j + s 1 1) {f [i] [j] = max (f[i-1] [k]) + j*a [i] (j 1 [k]) + j* a [i] (j* a[i] (j [i] [i] [i]] (j [i]] (j [=1 <================ k] [j] [j + j] [j] [j] [i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] 1<=k<=min(m,j+s-3-1)) 그리고 우리는 익숙한 데이터 구조의 단조로운 대기열로 최적화할 수 있다.이것은 복잡함을 O(n∗m) {O(n*m)} O(n∗m)로 안정시켰다!

#include
#define N 6000
#define int long long//      ,        signed main().
using namespace std;

int n,m,s;
int a[N],f[N][N],q[N],poi[N],ans=-1e17+7;
//q[]  f[][]  ,poi[]  f[][]    .

signed main()
{
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);

	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
		f[i][j]=-1e17+7;
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		int l=1,r=1;
		q[l]=f[i-1][m];
		poi[l]=m;
		for(int j=m;j>0;j--)//        
		{
			while(l<=r&&poi[l]>(s+j-1))l++;
			while(l<=r&&q[r]<f[i-1][j-1])r++;
			poi[++r]=j-1;
			q[r]=f[i-1][j-1];
			f[i][j]=q[l]+a[i]*j;
		}
	}
	for(int i=0;i<=m;i++)
	ans=max(ans,f[n][i]);
	cout<<ans<<endl;
	return 0;
}

그리고 AC!!!

이 블로그가 거물 DP 초보자들에게 도움이 되었으면 합니다.