最近在狂补题啊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<<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.