最大子矩陣問題的增強版～難度增加了不少！但是我莫名其妙地一次AC了……AC之后發現某個地方和我原本設計的算法不符……修改到和我設計的算法符合……然后WA了（這難道就是傳說中的RP么）。
我說說我AC的算法：首先，把原矩陣復制成4份，這樣就解決了矩陣循環的問題了；然后按照基礎最大子矩陣的方法枚舉上下邊，但是需要加入一個限制：上下邊的距離不能超過n（這個很好理解）；上下邊固定住以后，同樣和基礎最大子矩陣的做法一樣：DP。同時記錄當前序列的長度，長度如果等于n，從這個點到它前n個點的DP狀態需要重新計算（相當于
重新選定了當前行的起點，這樣會使算法復雜度增高到O(n^4)，不過長度等于n的情況太少啦，所以依然不會超時）。
后記：本人之前的算法還是可行的，只不過我代碼不小心寫錯啦～具體和上面的不同之處就在于檢測到長度等于n之后，計算當前點的狀態不再使用遞推，而改用枚舉序列起點的方式，兩種方法復雜度相同。
之前認為我本來的算法有誤是這樣想的：比如當前計算出一個[i,i+n-1]的序列，現在要計算i+n這一個點的狀態。直接枚舉[p,i+n]（其中i+1<=p<=i+n）這些序列即可。之前認為最優解可能出現在[i+1,p-1]這一段，所以需要重新從i+1開始遞推，后來想想是不可能出現這種情況的。
枚舉的方法修改成了如下代碼：
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;
}
posted on 2011-05-21 12:16
lee1r 閱讀(602)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃