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

10144 단어 문제풀이noipDPLuoGuDpNOIp
원제 전송문
  • 열거 현재 며칠째
  • 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;
}
    php의 arayphp로 맵 설치하기
    [LOJ6039] [아례훈련 2017 Day5] 보석(DP, 의사결정 단조성)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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