P2858 [USACO06FEB] 젖소 간식Treats for the Cows-동적 기획, 구간 dp

존은 젖을 많이 생산하는 젖소에게 특별 수당을 자주 주었다. 그래서 곧 젖소들은 어떻게 써야 할지 모르는 많은 돈을 가지게 되었다. 그래서 존은 N(1≤N≤2000)분의 맛있는 간식을 사서 젖소들에게 팔았다. 매일 존은 간식 한 개를 팔았다. 물론 존은 이 간식을 모두 팔아서 가장 큰 수익을 얻기를 희망했다. 이런 간식들은 다음과 같은 흥미로운 특성을 가지고 있다.
• 간식은 1..N 번호에 따라 일렬로 늘어서서 아주 긴 상자 안에 놓여 있다. 상자의 양쪽 끝에 구멍이 있다. 존은
하늘은 상자의 어느 한쪽에서 가장 바깥쪽의 하나를 꺼낼 수 있다.
• 맛있는 술과 맛있는 치즈와 비슷하다. 이 간식들은 오래 저장할수록 맛있다. 물론 존은 그것들을 더 높은 가격에 팔 수 있다.
• 각 간식의 초기 가치는 반드시 같지 않다. 존이 입고할 때 첫 번째 간식의 초기 가치는Vi(1≤Vi≤1000)이다.
• 제i분 간식이 구입 후 a일째에 판매되면vi×a．
Vi는 상자 꼭대기에서 아래로 내려오는 i번째 간식의 초기 가치입니다. 존은 모든 간식의 초기 가치를 알려주었습니다. 그리고 이 간식들이 모두 팔린 후에 그가 가장 많은 돈을 얻을 수 있는지 계산해 주셨으면 합니다.
이 문제는 왼쪽 몇 개를 취하고 오른쪽 몇 개를 취하는 것만이 결과에 영향을 미칠 수 있으므로 구간dp라고 생각하기 어렵지 않다
방법: f[i][j]는 i에서 j까지 최대 얼마를 얻을 수 있는지 나타낸다.
그러면 초기값 f[i][i]의 값은 마지막에 꺼내야 한다. 즉, v[i]*n이다.
세트: 매거 구간의 길이, 왼쪽 단점을 매거하여 오른쪽 단점을 구한다.
마지막으로 dp는 내외적으로 확대된 것으로 매번 가장 왼쪽 또는 가장 오른쪽을 고려하면 된다.
https://www.luogu.org/problemnew/show/P2858

#include
#include
#include
#include
using namespace std;
int v[2050];
int n;
int f[2050][2050];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i]);
	}
	for(int i=1;i<=n;i++){
		f[i][i]=v[i]*n;
	}
	for(int l=2;l<=n;l++){
		for(int i=1;i+l-1<=n;i++){
			int j=i+l-1;
			f[i][j]=max(f[i+1][j]+v[i]*(n-l+1),f[i][j-1]+v[j]*(n-l+1));
		}
	}
	printf("%d
",f[1][n]);
	return 0;
}