[문제풀이] 루구 5662: 기념품

원제 전송문

열거 현재 며칠째

d p i dp_i dpi는 오늘 원금이 i i i인 경우 오늘 사들이고 내일 팔면 가장 많은 이윤을 얻을 수 있다

즉, 제목의 뜻을 바꾸어 pi+1, j-3-pi, jp 를{i+1,j}-p_{i,j}pi+1,j-3pi,j를 하나의 아이템으로 간주

매거상품, dpk = max(dpk, dpi -3-pi, j+pi + 1, j -3-pi, j)(i는 며칠째, j는 상품, k는 원금) dpk=max(dp k, dp {i-p {i, j}}+p {i+1, j}-p {i, j})(i는 며칠째, j는 상품, k는 원금) dpk=max(dpk, dpi-3pi, j+pi+1, j-3pi, j)(i는 며칠째, j는 상품, k는 원금)

매일 금화 상한선 업데이트, m=m a x(m, m+d pm)m=max(m, m+dp m)m=max(m, m+dpm)

Code:

#include 
#define maxn 10010
using namespace std;
int t, n, m, p[110][110], dp[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s=  (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	t = read(), n = read(), m = read(); 
	for (int i = 1; i <= t; ++i)
		for (int j = 1; j <= n; ++j) p[i][j] = read();
	for (int i = 1; i < t; ++i){
		memset(dp, 0, sizeof(dp));
		for (int j = 1; j <= n; ++j)
			for (int k = p[i][j]; k <= m; ++k) dp[k] = max(dp[k], dp[k - p[i][j]] + p[i + 1][j] - p[i][j]);
		m = max(m, dp[m] + m);
	}
	printf("%d
", m);
	return 0;
}