기관차--사고방식과 문제풀이

11507 단어 DP가방

도입부:


왜 이 문제를 썼을까요?이 문제는 비록 간단하지만, 나는 내가 헛소리를 쓰고 싶다고 생각한다!이 문제 때문에, 일부 세부 사항은 정말 우리가 주목할 만한 것이다.
제목.

아이디어:


가장 큰 인원을 끌어올릴 수 있도록 요구하고 연속적이어야 하며 오른쪽으로 가야 하기 때문에 이 문제는 대체로 가장 긴 상승자 서열 쪽으로 생각할 수 있다.그래서 상태 이동 방정식은 다음과 같다.
  dp[i][j] = max(dp[i][j - 1],dp[i - 1][j - m] +b[j] - b[j - m]);

이 방정식의 뜻은 i차 앞부분에 있을 때 j차를 끌 수 있다는 것이다.

디테일 하나 주의!1층 순환은 차머리를 매거하는 수량이다

for(int i=1;i<=3;i++)

2층 순환은 매거진으로 i차 앞을 끌 때 m칸을 끌 수 있는 사람이 가장 많다

for(int j=m;j<=n;j++)

질문: 왜 j는 m부터 시작해야 합니까?


제목이 알려줬으니까>＿<
하나의 정수 m는 단일 기관차에 끌릴 수 있는 최대 화차 개수를 대표한다

그럼 왜 j<=n인가요?


제목도 알려줬으니까>＿<

그래서 목표는 세 번째 차 앞부분에 n칸을 당겨야 가장 많은 인원을 확보할 수 있다는 것이다.


그래서 마지막 출력은 아마...
printf("%d
",dp[3][n]);

코드:

//QAQ
#include
#include 
#include
using namespace std;
int dp[5][50005],a[50005],b[50005];
int max(int x,int y){
    if (x>y) return x;
    else return y;
}
int main(){
	int m,t,n;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			b[i]=b[i-1]+a[i];
		}
		scanf("%d",&m);
		for(int i=1;i<=3;i++){//   i     
			for(int j=m;j<=n;j++){ // i    ，   m       （3*m<=n） 
				dp[i][j] = dp[i][j - 1];
                dp[i][j] = max(dp[i][j - 1],dp[i - 1][j - m] +b[j] - b[j - m]);
			}
		}
		printf("%d
",dp[3][n]);
	}
	return 0;
}

본인의 능력에 대한 문제도 어떻게 말해야 할지 몰라서 세부적인 부분도 있었다.


그래서 또 모르는 것이 있으면 본인에게 물어봐도 된다.이렇게 하자.

웹 사이트를 폭발 속도로 어둡게 만들기 (Darmode.js)
Fork 한 Repository 최신 상태로 동기화하기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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