首页 > 代码库 > 【NOIP2014】子矩阵
【NOIP2014】子矩阵
这题如果按暴力做只有一半分，最大时间复杂度为O(C(8,16)*C(8,16)); 很容易算出超时；
我们可以发现如果直接dp会很难想，但是知道选哪几行去dp就很好写状态转移方程：
dp[i][j]=min(dp[i][j],dp[k][j-1]+a[i]+b[k][i]);
其中dp[i][j]表示 前i列里选j列的子矩阵最大分值
a[i]表示 第i列选到的行的总差值
b[k][i]表示选到的每一行第k列和第i列之间的差值
我们只要枚举 行 然后dp一次，取最小值即可 这样最大时间复杂度就成了O(C(8,16)*n3);
最后附上我弱弱的pascal代码：
1 var 2 i,j,k,n,m,n1,m1,ans:longint; 3 dp,a,f:array[0..16,0..16] of longint; 4 hc:array[0..16,1..16,1..16] of longint; 5 b,lc:array[0..17] of longint; 6 function min(a,b:longint):longint; 7 begin 8 if a>b then min:=b 9 else min:=a;10 end;11 procedure ddp;12 var13 i,j,k,max:longint;14 begin15 fillchar(f,sizeof(f),0);16 fillchar(lc,sizeof(lc),0);17 fillchar(dp,sizeof(dp),0);18 for i:=1 to m do19 for j:=1 to n1-1 do20 lc[i]:=lc[i]+abs(a[b[j+1],i]-a[b[j],i]);21 for i:=1 to m do22 for j:=i+1 to m do23 for k:=1 to n1 do24 f[i,j]:=f[i,j]+hc[b[k],i,j];25 for i:=1 to m do26 dp[i,1]:=lc[i];27 for i:=2 to m do28 for j:=2 to m1 do29 if i>=j then30 begin31 dp[i,j]:=maxlongint;32 for k:=j-1 to i-1 do33 dp[i,j]:=min(dp[i,j],dp[k,j-1]+lc[i]+f[k,i]);34 end;35 for i:=m1 to m do36 if dp[i,m1]<ans then ans:=dp[i,m1];37 end;38 procedure jw(ii:longint);39 begin40 inc(b[ii]);41 if ii>=0 then42 if b[ii]>(n-n1+ii) then43 begin44 jw(ii-1);45 b[ii]:=b[ii-1]+1;46 end;47 end;48 begin49 read(n,m,n1,m1);50 for i:=1 to n do51 for j:=1 to m do52 begin53 read(a[i,j]);54 for k:=1 to j-1 do55 hc[i,k,j]:=abs(a[i,j]-a[i,k]);56 end;57 for i:=1 to n1 do58 b[i]:=i;59 ans:=100000000;60 while b[0]=0 do61 begin62 ddp;63 jw(n1);64 end;65 write(ans);66 end.
【NOIP2014】子矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。