最大子矩陣問(wèn)題的增強(qiáng)版～難度增加了不少！但是我莫名其妙地一次AC了……AC之后發(fā)現(xiàn)某個(gè)地方和我原本設(shè)計(jì)的算法不符……修改到和我設(shè)計(jì)的算法符合……然后WA了（這難道就是傳說(shuō)中的RP么）。
我說(shuō)說(shuō)我AC的算法：首先，把原矩陣復(fù)制成4份，這樣就解決了矩陣循環(huán)的問(wèn)題了；然后按照基礎(chǔ)最大子矩陣的方法枚舉上下邊，但是需要加入一個(gè)限制：上下邊的距離不能超過(guò)n（這個(gè)很好理解）；上下邊固定住以后，同樣和基礎(chǔ)最大子矩陣的做法一樣：DP。同時(shí)記錄當(dāng)前序列的長(zhǎng)度，長(zhǎng)度如果等于n，從這個(gè)點(diǎn)到它前n個(gè)點(diǎn)的DP狀態(tài)需要重新計(jì)算（相當(dāng)于
重新選定了當(dāng)前行的起點(diǎn)，這樣會(huì)使算法復(fù)雜度增高到O(n^4)，不過(guò)長(zhǎng)度等于n的情況太少啦，所以依然不會(huì)超時(shí)）。
后記：本人之前的算法還是可行的，只不過(guò)我代碼不小心寫(xiě)錯(cuò)啦～具體和上面的不同之處就在于檢測(cè)到長(zhǎng)度等于n之后，計(jì)算當(dāng)前點(diǎn)的狀態(tài)不再使用遞推，而改用枚舉序列起點(diǎn)的方式，兩種方法復(fù)雜度相同。
之前認(rèn)為我本來(lái)的算法有誤是這樣想的：比如當(dāng)前計(jì)算出一個(gè)[i,i+n-1]的序列，現(xiàn)在要計(jì)算i+n這一個(gè)點(diǎn)的狀態(tài)。直接枚舉[p,i+n]（其中i+1<=p<=i+n）這些序列即可。之前認(rèn)為最優(yōu)解可能出現(xiàn)在[i+1,p-1]這一段，所以需要重新從i+1開(kāi)始遞推，后來(lái)想想是不可能出現(xiàn)這種情況的。
枚舉的方法修改成了如下代碼：
if(len==n)
{
now=-kInf;
len=0;
for(int p=k-n+1;p<=k;p++)
{
if(now<d[j][k]-d[j][p-1]-d[i-1][k]+d[i-1][p-1])
{
now=d[j][k]-d[j][p-1]-d[i-1][k]+d[i-1][p-1];
len=k-p+1;
}
}
tmp=max(tmp,now);
}
以下是我的代碼：
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(77);
const int kInf(0x7f7f7f7f);
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int r[kMaxn<<1][kMaxn<<1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&r[i][j]);
for(int i=1;i<=n;i++)
for(int j=n+1;j<=(n<<1);j++)
r[i][j]=r[i][j-n];
for(int i=n+1;i<=(n<<1);i++)
for(int j=1;j<=n;j++)
r[i][j]=r[i-n][j];
for(int i=n+1;i<=(n<<1);i++)
for(int j=n+1;j<=(n<<1);j++)
r[i][j]=r[i-n][j-n];
int d[kMaxn<<1][kMaxn<<1];
memset(d,0,(kMaxn<<1)*(kMaxn<<1)*sizeof(int));
for(int i=1;i<=(n<<1);i++)
for(int j=1;j<=(n<<1);j++)
d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+r[i][j];
int ans(-kInf);
for(int i=1;i<=(n<<1);i++)
for(int j=i;j<=(n<<1) && j<=i+n-1;j++)
{
int t[kMaxn<<1];
for(int k=1;k<=(n<<1);k++)
t[k]=d[j][k]-d[j][k-1]-d[i-1][k]+d[i-1][k-1];
int tmp(-kInf),now(-kInf),len(0);
for(int k=1;k<=(n<<1);k++)
{
if(len==n)
{
now=-kInf;
len=0;
for(int p=k-n+1;p<=k;p++)
{
if(now+t[p]>t[p])
{
now=now+t[p];
len++;
}
else
{
now=t[p];
len=1;
}
tmp=max(tmp,now);
}
}
else
{
if(now+t[k]>t[k])
{
now=now+t[k];
len++;
}
else
{
now=t[k];
len=1;
}
tmp=max(tmp,now);
}
}
ans=max(ans,tmp);
}
printf("%d\n",ans);
}
return 0;
}