noip吧 关注：25,180贴子：642,099
第三题：螺旋矩阵
方法一：模拟法
按照题目说的那样，模拟数字生成的过程，碰到i,j就输出。不过最坏情况是碰到最后的那个数，即n^2，由于小于等于30000，超时是不可避免的。不过这种方法易于理解，也很容易做出来。很多人都是这么做的。
空间复杂度：O(1)
时间复杂度：O(n^2)
预计得分：50~70
方法二：数学方法
数学方法有很多，现在说说我的做法。
先读入4个数，通过i,j，判断出那个数在第几个圈里。然后递推，得出那个圈的开始数和末尾数。再通过i,j，计算出那个数是那个圈的第几个数，然后加上那个圈开头数，输出。
这个算法差不多想了我40分钟，我知道是很复杂，但是也是一种解决办法。肯定有更简单的方法的，你可以在下面提出。
空间复杂度：O(1)
时间复杂度：O(n/2)
预计得分：100
方法一：模拟法
按照题目说的那样，模拟数字生成的过程，碰到i,j就输出。不过最坏情况是碰到最后的那个数，即n^2，由于小于等于30000，超时是不可避免的。不过这种方法易于理解，也很容易做出来。很多人都是这么做的。
空间复杂度：O(1)
时间复杂度：O(n^2)
预计得分：50~70
方法二：数学方法
数学方法有很多，现在说说我的做法。
先读入4个数，通过i,j，判断出那个数在第几个圈里。然后递推，得出那个圈的开始数和末尾数。再通过i,j，计算出那个数是那个圈的第几个数，然后加上那个圈开头数，输出。
这个算法差不多想了我40分钟，我知道是很复杂，但是也是一种解决办法。肯定有更简单的方法的，你可以在下面提出。
空间复杂度：O(1)
时间复杂度：O(n/2)
预计得分：100
lz的和我差不多 不过第二题真的不会有精度问题么
第四题满分算法：
var w,r,minn,i,j,n,m:longint;
c:array[0..16] of longint;
a,b,s,f:array[0..16,0..16] of longint;
function min(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
procedure dp;
var i,sum,j,k:longint;
begin
fillchar(s,sizeof(s),0);
for i:=1 to m do
for j:=1 to i do
begin
for k:=1 to r do s[i,j]:=s[i,j]+abs(b[k,i]-b[k,j]);
for k:=1 to r-1 do s[i,j]:=s[i,j]+abs(b[k,i]-b[k+1,i]);
end;
fillchar(f,sizeof(f),12);
for i:=1 to m do f[1,i]:=s[i,i];
for i:=2 to w do
for j:=i to m-w+i do
for k:=i-1 to j-1 do
f[i,j]:=min(f[i,j],f[i-1,k]+s[j,k]);
for i:=w to m do
minn:=min(minn,f[w,i])
end;
procedure dfsr(x,s:longint);
var i:longint;
begin
if s=r then
begin
dp;
exit;
end;
if x=n+1 then exit;
for i:=0 to 1 do
begin
if i=1 then b[s+1]:=a[x];
dfsr(x+1,s+i);
end;
end;
begin
assign(input,'submatrix.in');
reset(input);
assign(output,'submatrix.out');
rewrite(output);
readln(n,m,r,w);
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
minn:=maxlongint;
dfsr(1,0);
writeln(minn);
close(input);
close(output);
end.
var w,r,minn,i,j,n,m:longint;
c:array[0..16] of longint;
a,b,s,f:array[0..16,0..16] of longint;
function min(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
procedure dp;
var i,sum,j,k:longint;
begin
fillchar(s,sizeof(s),0);
for i:=1 to m do
for j:=1 to i do
begin
for k:=1 to r do s[i,j]:=s[i,j]+abs(b[k,i]-b[k,j]);
for k:=1 to r-1 do s[i,j]:=s[i,j]+abs(b[k,i]-b[k+1,i]);
end;
fillchar(f,sizeof(f),12);
for i:=1 to m do f[1,i]:=s[i,i];
for i:=2 to w do
for j:=i to m-w+i do
for k:=i-1 to j-1 do
f[i,j]:=min(f[i,j],f[i-1,k]+s[j,k]);
for i:=w to m do
minn:=min(minn,f[w,i])
end;
procedure dfsr(x,s:longint);
var i:longint;
begin
if s=r then
begin
dp;
exit;
end;
if x=n+1 then exit;
for i:=0 to 1 do
begin
if i=1 then b[s+1]:=a[x];
dfsr(x+1,s+i);
end;
end;
begin
assign(input,'submatrix.in');
reset(input);
assign(output,'submatrix.out');
rewrite(output);
readln(n,m,r,w);
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
minn:=maxlongint;
dfsr(1,0);
writeln(minn);
close(input);
close(output);
end.
