2794 - 挖宝藏
某片矿区含有丰富的矿产资源，有金银铜铁锡等，还有钻石呢。很多人前去淘金。你现在手上有一笔资金，可买到该矿山面积为S平方米的地域进行开采，你通过秘密途径搞到一份绝密资料，那就是该矿山的资源分布图。有了这些资料后，你准备买下哪块地进行开采，才能得到最大的效益。
Input
第一行为一个整数N（N<=100），表示矿山的边长。接下来是矿山的资源分布图，按单位平方米标记了每个点开采的价值，若为负数，表示开采将会亏本。最后一行为一个整数S，表示你可开采的面积（S<10000）
Output
输出开采后你的最大收益，注意你最大可以买S，你也可以买小于S的面积。为了规划，买的地域必须成矩型。
Examples
Input
3 1 2 3 -1 2 4 -3 -2 3 4
Output
11
Solution C++
#include <cstdio> #define maxn 101 int n , S , ans = 0 ; int sum[maxn][maxn] = {0} ; int main() { scanf("%d", &n ); int t ; for (int i = 1 ; i <= n ; i ++ ) { for (int j = 1 ; j <= n ; j ++ ) { scanf("%d", &t ) ; for (int p = i ; p <= n ; p ++ ) { for (int q = j ; q <= n ; q ++ ) { sum[p][q] += t ; //printf("s[%d][%d] = %d\n",p,q,sum[p][q]); } } } } scanf("%d", &S ) ; if (S > n*n) S=n*n; for (int s = 1 ; s <= S ; s ++ ) { for (int a = 1 ; a <= s ; a ++ ) { int b = s/a ; if (a*b != s) continue ; for (int i = 1 ; i <= n-a+1 ; i ++ ) { for (int j = 1 ; j <= n-b+1 ; j ++ ) { int i2 = i+a-1 , j2 = j+b-1 ; int t = sum[i2][j2]-sum[i-1][j2]-sum[i2][j-1]+sum[i-1][j-1]; if (t > ans) ans = t ; } } } } printf("%d\n",ans); return 0 ; }