[TIOJ] 1277. 俄羅斯娃娃－續

題目連結:http://tioj.infor.org/problems/1277

---

本題等價於做最大子矩陣，而最大子矩陣就等於說枚舉所有高度的矩陣，並把他們都壓起來(同一位加一起)後做最長遞增子序列

#include <stdio.h>
#include <vector>

using std::vector;

vector<long long> matrix[500 + 10];

int main(){
	long long size, max=0, cur=0;
	scanf("%d",&size);
	for(int j=0;j<size;j++){
		matrix[0].push_back(0);
		scanf("%lld", &matrix[0][j]);
		if(cur<0)
			cur=0;
		cur += matrix[0][j];
		if(cur>max)
			max=cur;
	}
	for(int i=1;i<size;i++){
		cur = 0;
		for(int j=0;j<size;j++){
			matrix[i].push_back(0);
			long long t;
			scanf("%lld", &t);
			matrix[i][j] = matrix[i-1][j] + t;
			if(cur<0)
				cur=0;
			cur += matrix[i][j];
			if(cur>max)
				max=cur;
		}
		for(int k=1;k<=i;k++){
			cur=0;
			for(int j=0;j<size;j++){
				if(cur<0)
					cur=0;
				cur += (matrix[i][j] - matrix[i-k][j]);
				if(cur>max)
					max=cur;
			}
		}
	}
	printf("%lld\n", max);
	return 0;
}