사탕통【DP】

8367 단어 DP
> Description n*m 칸으로 나뉘어진 사탕 상자, i행 j열 위치의 칸에는 a[i][j]개의 사탕이 들어 있다.텐시는 이 사탕을 한 PPMM에게 주려고 했지만 사탕 상자를 보내기 전날 밤 얄미운 쥐 한 마리가 사탕 상자를 야습해 체크가 일부 약탈되고 구멍을 뚫었다.텐시는 가능한 한 빨리 이 사탕 상자에서 직사각형 사탕 상자를 잘라내야 합니다. 새 사탕 상자에는 구멍이 나지 않습니다. 또한 텐시는 새 사탕 상자 안에 있는 사탕의 총수를 최대한 많이 보존하기를 바랍니다.텐시가 새 사탕 상자에서 얼마나 많은 사탕을 보존할 수 있는지 계산하는 프로그램을 설계해 주세요.
> Input 파일 CANDY.IN에서 데이터를 읽습니다.첫 줄에는 두 개의 정수 n, m가 있다.i+1행의 j개수는 a[i][j]를 나타내고, 만약 이 수가 0이면 이 위치의 칸이 약탈되었다는 것을 나타낸다.그중:1≤n,m≤3000≤a[i][j]≤255
> 아웃풋에서 최대 캔디를 캔디까지 출력한다.OUT.
> Sample Input 3 4 1 2 3 4 5 0 6 3 10 3 4 0
> Sample Output 17
주:10,3,4 이 직사각형의 사탕 수가 가장 크다
> Hint 데이터 크기: 40% 데이터 1≤n, m≤300
> 문제풀이 사고방식이라는 문제는 가장 큰 서브 매트릭스에서 가장 큰 서브 매트릭스를 구하는 변식이다. 나는 바로 계산에 판단을 추가했다.
> 코드
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=301;
int a[maxn][maxn],len[maxn][maxn];
int ans,n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
     	scanf("%d",&a[i][j]);
     	len[i][j]=len[i-1][j]+a[i][j];
     }
    for(int i=1;i<=n;i++)
     for(int j=i;j<=n;j++)
     {
     	int sum=0;
     	for(int k=1;k<=m;k++)
     	{ 
     	    bool ca=true;
     	    for(int kk=i;kk<=j;kk++)
     	     if(a[kk][k]==0) {ca=false; break;}
     	     //  :  i j k   0,        
			if(ca==false) sum=0;
			 else sum+=len[j][k]-len[i-1][k];
			if(ans<sum) ans=sum;
     	}
     }
    printf("%d",ans);
	return 0;
}

좋은 웹페이지 즐겨찾기