最大子矩阵问题的增强版～难度增加了不少！但是我莫名其妙地一次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 阅读(563)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划