NOIP2014 T4 子矩阵 dfs+dp

最近在狂补题啊QAQ...

打算先把NOIP的干掉吧...

点我看题

链接还是放洛谷的了...

题意：给一个n*m的矩阵，在这个矩阵里选 r 行 c 列，然后这 r 行 c 列所相交的格子为新矩阵的，设定矩阵的价值为矩阵中相邻（上下左右）的元素的差的绝对值。

求最小的价值。

思路：这题我还很清楚在今年NOIP集训前lz有讲过，但是没听懂啊QAQ...昨天去看了看，想着先打个暴力水分。

因为比赛中暴力分很关键啊...练好暴力很重要。直接先打了一个裸的双重dfs。拿了55分。

当然这都是普通的暴力分。要知道暴力打的好，捞分没烦恼。所以我就开始想剪枝优化了...加了个简单的普遍优化，就多水到了10分。一个暴力能比别人多10分，差距其实也挺大的了。

然后就是正解了，正解当然是dp不错，但是对于不确定行且不确定列来dp是十分困难的，然后你会发现，其实数据很小啊，能不能保留一个dfs，然后另一个改成dp...

显然这样之后时间复杂度成功满足，而且还确定了行。

所以考虑列就行了。

我萌设 f[i,j] 表示以 i 结尾，选了 j 列的最优值。

怎么转移？ f[i,j]的前驱状态我萌可以在花一重去枚举，即 f[k,j-1] 这样的话方程就出来了。

设num[i] 表示在已知行的情况下，在第 i 列中行于行之间的价值。

设cost[i,j] 表示在已知行的情况下，第 i 列中的每行和第 j 列中的每行的价值。

这样的话方程就是

f[i,j]=min(f[k,j-1]+num[i]+cost[k,i]) (1≤k≤i-1)

然后答案就是枚举每一列，取 ans=min(ans,f[i,c]) (1≤i≤m)

对于每一种行的排列进行这样的dp取最小的ans就是答案。

这题还是很好的，成功涨了姿势，对于多维的时候，可以考虑使用 dfs 降成一维再进行dp...

当然辣！我是悄悄咪咪看了题解的。

var
  i,j,k:longint;
  user,num:array[0..20]of longint;
  f,cost,a:array[0..20,0..20]of longint;
  n,m,r,c:longint;
  ans:longint;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
procedure dp;
var  i,j,k:longint;
begin
  for i:=1 to m do
  begin
    num[i]:=0;
    for j:=2 to r do
    inc(num[i],abs(a[user[j],i]-a[user[j-1],i]));
    for j:=1 to i-1 do
    begin
      cost[j,i]:=0;
      for k:=1 to r do
      cost[j,i]:=cost[j,i]+abs(a[user[k],j]-a[user[k],i]);
    end;
  end;
  for i:=1 to m do
  begin
    for j:=2 to c do
    f[i,j]:=1 <<25;
    f[i,1]:=num[i];
  end;
  for i:=2 to m do
    for j:=2 to c do
    for k:=1 to i-1 do
    f[i,j]:=min(f[k,j-1]+cost[k,i]+num[i],f[i,j]);
  for i:=2 to m do
  if ans>f[i,c] then ans:=f[i,c];
end;
procedure dfs(dep,last:longint);
var i:longint;
begin
  if dep=r then
  begin
    dp;
    exit;
  end;
  for i:=last+1 to n do
  begin
    user[dep+1]:=i;
    dfs(dep+1,i);
  end;
end;
begin
  read(n,m,r,c);
  for i:=1 to n do
    for j:=1 to m do
    read(a[i,j]);
    ans:=1 << 25;
  dfs(0,0);
  writeln(ans);
end.

NOIP2014 T4