#算法
由总结二可知，我们可以像方格取数那样dp路径，顺便维护额外店铺的信息；
由总结三可知，dp时我们要知道（i，j）这个店铺的信息，还要知道它父亲的信息，更要知道它父亲的父亲的信息；
由总结四可知，dp时我们必须要知道（i，j）这个店铺是怎么过来的（这样才能买额外店铺）。
又因为共享时额外店铺只在右方或下方，那么如果买了上方和左方的店铺是没有后效性的，右方或下方的店铺可以由不得已的时候（下面的dp）再买，所以我们在dp时可以只买上方和左方的店铺，右方和下方的店铺会成为下层dp的上方和左方，所以可以暂时不买~
由此推出转移方程—— dp[dir][i][j][c1][c2] dir=[0,1] c1=[0,2] c2=[0,1]；
dir表示（i，j）这个店铺是从父亲那里怎么走过来的，0表示向下，1表示向右；
c1表示（i，j）这个店铺还差多少个店铺（包括路径上的店铺）才能符合题目要求；
c2表示（i，j）这个店铺的父亲还差多少个店铺（包括路径上的店铺）才能符合题目要求；
dp[dir][i][j][c1][c2]表示按dir方向走到（i，j）时，~c1~,~c2~，的最小花费。
下面以dir==0（向下走）为例，dir==1类似，并设（i，j）这个店铺要买Cnt的店铺（包括路径上的店铺）才满足题目要求。
很显然，如果（i，j）这个店铺开张了，那么就可以更新它父亲（i-1，j）的信息（需要买的店铺-1），否则就不能更新；
如果它父亲（i-1，j）这个店铺开张了，那么就可以更新它本身的信息（需要买的店铺-1），否则就不能更新。
dp[0][i][j][ Cnt-(bool)shop[i-1][j] ][c2] = dp[0/1][i-1][j][ c2+(bool)shop[i][j] ][0]+shop[i][j]； c2=[0,1]
其他情况如下：
1.（i，j）的父亲是从左边走过来的。
----- -----
| 路径 | 路径 |
----- -----
| ？ | 路径 |
----- -----
对于？所在的店铺（i，j-1），如果它开张了，那么它本身就可以更新（i-1，j-1）和（i，j）的信息。
if (shop[i][j])
dp[0][i][j][ Cnt-1-(bool)shop[i-1][j] ][c2] =min（dp[0][i][j][ Cnt-(bool)shop[i-1][j] ][c2] ， dp[1][i-1][j][ c2+(bool)shop[i][j] ][1] ）+ shop[i][j] + shop[i][j-1];
2.（i，j）的父亲是从上面走过来的。
----- -----
| 路径 | 1 |
----- -----
| 路径 |
----- -----
| 2 | 路径 |
----- -----
一，对于1所在的店铺，由于在dp时没有考虑，现在再不考虑就会永远丢失其信息，但它又是有可能作为（i-2，j）的额外店铺的，所以此时要更新
if (shop[i-2][j+1])
dp[0][i][j][ Cnt-(bool)shop[i-1][j] ][c2] = dp[0][i-1][j][ c2+(bool)shop[i][j] ][1]+ shop[i][j] + shop[i-2][j+1];
二，对于2所在的店铺，它可以更新（i，j）的信息，但要注意，此时不能更新它父亲的父亲（i-2，j）的信息；
if (shop[i][j-1])
dp[0][i][j][ Cnt-1-(bool)shop[i-1][j] ][c2] =min（dp[0][i][j][ Cnt-(bool)shop[i-1][j] ][c2] ， dp[0][i-1][j][ c2+(bool)shop[i][j] ][0] ）+ shop[i][j] + shop[i][j-1];
3.另外，如果c2==0，此时无论（i，j）是否开张都要更新它父亲的信息（路径延伸），转移方程和上述的差不多~
#结束语
至此我们已经dp完了~
时间复杂度O(nm)。。。不是很懂题目所说的卡常是什么意思。。。
由于本人代码风格不佳，所以就不粘出来了~
by Zayin2653457495 @ 2016-10-18 17:33:30
有些空格被吞了看懂就行不要介意~
by Zayin2653457495 @ 2016-10-18 17:34:32
沙发
by loli @ 2016-10-18 20:22:41