nyoj題是漢語的，很好理解，該題就是在一個矩陣中找到一個子矩陣，該子矩陣和最大！！輸出最大和即可。。
思路：
首先你可能會想到窮舉的方法，但當n很大時，顯然是不可取的。。這個題應該是用dp來解決的。
讓我們先來看另外的一個問題(最大子段和問題)： 給定一個長度為n的一維數組a，請找出此數組的一個子數組,使得此子數組的和sum＝a[i]+a[i+1]+……+a[j]最大，其中i>=0,i<n,j>=i,j<n，例如 31 -41 59 26 -53 58 97 -93 -23 84 子矩陣59+26-53+58+97=187為所求的最大子數組。這個題會寫吧，簡單的dp。
代碼：
[cpp]
int maxSubArray(int n,int a[])
{
int b=0,sum=-10000000;
for(int i=0;i<n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}//動態規劃。
聯系本題，二者區別呢？一個是一維的，一個是多維的，那麼把多維轉化為一維不就可以ac了。。
假設最大子矩陣的結果為從第r行到k行、從第i列到j列的子矩陣，如下所示(ari表示a[r][i],假設數組下標從1開始)：
| a11 …… a1i ……a1j ……a1n |
| a21 …… a2i ……a2j ……a2n |
| . . . . . . . |
| . . . . . . . |
| ar1 …… ari ……arj ……arn |
| . . . . . . . |
| . . . . . . . |
| ak1 …… aki ……akj ……akn |
| . . . . . . . |
| an1 …… ani ……anj ……ann |
那麼我們將從第r行到第k行的每一行中相同列的加起來，可以得到一個一維數組如下：
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
由此我們可以看出最後所求的就是此一維數組的最大子斷和問題，到此我們已經將問題轉化為上面的已經解決了的問題了。
nyoj 和 poj 題目基本一樣，只是輸入格式 有區別，這裡只給出 nyoj 的 代碼。。
[cpp]
#include<stdio.h>
#include<string.h>
int ans[200][200];
int n,m,max;
void find (int k)
{
int i,j,t=0;
for(i=1;i<=m;i++)
{
if(t>0)
t+= ans[k][i];
else
t= ans[k][i];
if(t>max)
max=t;
}
}
int main()
{
int a,b,c,ncase;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%d%d",&n,&m);
for(a=1;a<=n;a++)
{
for(b=1;b<=m;b++)
scanf("%d",&ans[a][b]);
}
max=ans[1][1];
for(a=1;a<=n;a++)
{
find(a);
for(b=a+1;b<=n;b++)
{
for(c=1;c<=m;c++)
{
ans[a][c]+=ans[b][c];
}
find(a);
}
}
printf("%d\n",max);
}
}
作者：PIAOYI0208
