백준 17397 FLEX

https://www.acmicpc.net/problem/17397

숭고한 공식 풀이는 여기서 보실 수 있습니다.

다이나믹 프로그래밍 문제입니다. 오늘 날짜, 남은 돈, 분배 받은 돈 3개의 원소를 이용하여 memoization할 수 있습니다.

점화식은 $ memo[n][m][c]=min(memo[n-1][m-i][i]+stress)$ 라고 할 수 있고,

i가 10 이하이므로(지출 예상 비용이 10 이하이므로 10보다 더 많이 쓸 필요는 없습니다.)

시간복잡도는 $ O(n\times m\times c \times c) $가 됩니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=1005;
int memo[SZ][205][12];
int arr[SZ];
int n,m;
int stress(int x, int y){
	return x>y?(x-y) * (x-y):0;
}
int dp(int p, int rem, int dif){
	if(p==n) return 0;
	if(memo[p][rem][dif]!=-1) return memo[p][rem][dif];
	int mn=INT_MAX;
	for(int i=0;i<=min(10,rem);i++){
		mn=min(mn,dp(p+1,rem-i,i)+stress(arr[p]+dif,arr[p+1]+i));
	}
	return memo[p][rem][dif]=mn;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	memset(memo,-1,sizeof(memo));
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>arr[i];
	cout<<dp(1,m,0);
	return 0;
}