다차원 구해 최대 하위 행렬과 (접두사 + 압축 + DP)

이런 문제를 풀려면 규칙을 찾아야 한다. 우선 차원이 1일 때의 이 문제를 살펴보자.① 차원이 1일 때.이 문제는 최대 연속 하위 세그먼트 및 를 구하는 것으로 변경됩니다.이때 동적 기획으로 이 문제를 해결할 수 있다.동적 기획의 사고방식도 매우 간단하다. 1: 상태 dp[i]는 A[i]를 끝으로 하는 연속 서열의 최대 합을 나타낸다(여기서 A[i]는 반드시 연속 서열의 끝으로 해야 한다).단계2: 다음과 같이 고려한다. dp[i]는 반드시 A[i]로 끝내야 하는 연속 서열을 요구하기 때문에 두 가지 상황만 있다. 이 가장 큰 것과 가장 큰 연속 서열은 단지 하나의 요소, 즉 A[i]로 시작하고 A[i]로 끝난다.이 최대 화합의 연속 서열에는 여러 가지 요소가 있는데 그것이 바로 앞의 A[p]에서부터 (p가 첫 번째 상황에 가장 큰 화합은 A[i] 자체이다. 두 번째 상황에 가장 큰 화합은 dp[i-1]+A[i]이다. 그래서 상태 이동 방정식을 얻었다. dp[i]=max{A[i], dp[i-1]+A[i]} 그러면 최대 연속 자단과 핵심 코드는 다음과 같다.

for (int i=1;i<=n;i++){
  dp[i]=max(a[i],a[i]+dp[i-1]);
  ans=max(ans,dp[i]);
  }
  cout<<ans<<endl;

차원이 1일 때는 매우 간단하지만, 차원이 2일 때는 어떻게 해야 하나요?② 차원이 2일 때.문제는 하나의 매트릭스에서 그의 매트릭스를 찾는 것이다. 이 매트릭스는 모든 매트릭스에서 가장 크다.우선 폭력의 매거를 생각하면 복잡도는 O(N*N*M*M*Sum)이다. 그 중에서 최적화되지 않으면 Sum을 요구하는 것도 어렵다.그럼 우선 접두사를 사용해서Sum의 시간 복잡도를 최적화합시다.중성자 행렬의 합을 구하려면 틀림없이 여러 번 물어봐야 한다.그럼 가장 좋은 해결 방법은 접두사와무엇이 접두사와?a[i][j]를 제j열 전 i행의 합으로 설정합니다.우리는 1차원의 최대 연속 자단과 경험을 얻었다. 우리는 차원을 분리하여 그 중의 1차원을 열거한 다음에 DP로 다른 1차원을 스캔할 수 있다. 이렇게 하면 복잡도를 O(N*M*M) 가설의 매개 x차원, 핵심 코드로 낮출 수 있다.

ll sqsum(int x1,int x2,int s){
	return  a[x2][s] - a[x1][s];
}
int main(){
	for(int j=1;j<=k;j++)
		for(int i=1;i<=c;i++)
			a[i][j] += a[i-1][j];
	for(int i=1;i<=k;i++)
			for(int j=i;j<=k;j++){
				memset(dp,0,sizeof(dp));
					for(int v =1 ;v<=g;v++){
						dp[v] = max(dp[v-1],0) + sqsum(i,j,v);
							 anss=max(anss,dp[v]);
							}
					}
		cout<<anss<<endl;
}

앞의 2차원이 있으면 3차원은 매우 쉽다.③ 차원이 3 일 때.앞의 경험을 통해 차원이 3일 때 2차원 중의 모든 행렬을 열거하고 3차원에 대해 DP를 스캔하면 된다.이때 접두사와 a[i][j][k]는 K 차원에서의 a[0][j][k]~a[i][j][k]의 합에 a[i][0][k]~a[i][j][k]의 합을 더한다.그렇다면 (x1, y1)을 왼쪽 상단 좌표와 (x2, y2)를 오른쪽 하단 좌표로 하는 하위 행렬의 모든 원소와간단해졌어.이때의 합은 a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1](이때 a는 접두어와 a) 마찬가지로 마지막 차원의 O(n^2)의 복잡도를 O(n)로 낮출 수 있다. 매거의 복잡도는 변하지 않고 O(N*N*M*M)로 전체적인 복잡도는 O(N^5) 핵심 코드이다.

ll sqsum(int x1,int y1,int x2,int y2,int s){
	return a[x2][y2][s] + a[x1-1][y1-1][s]  - a[x1-1][y2][s]  - a[x2][y1-1][s] ;
}
int main(){
	for(int l=1;l<=g;l++)
		for(int i=1;i<=c;i++)
			for(int j=1;j<=k;j++)
				a[i][j][l] += a[i-1][j][l] + a[i][j-1][l] - a[i-1][j-1][l];
	for(int i=1;i<=c;i++)
			for(int j=1;j<=k;j++)
				for(int p = 1;p <= i;p++)
					for(int q = 1;q <= j;q++){
						memset(dp,0,sizeof(dp));
						for(int v =1 ;v<=g;v++){
							dp[v] = max(dp[v-1],0) + sqsum(p,q,i,j,v);
							 anss=max(anss,dp[v]);
						}
					}
		cout<<anss<<endl;
}