2014蓝桥杯B组c/c++预赛 第九题地宫取宝 (四维线性dp) - Tc_To_Top的专栏 - 博客频道 - CSDN.NET
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入格式
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
输出格式
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
样例输入
2 2 2
1 2
2 1
样例输出
2
样例输入
2 3 2
1 2 3
2 1 5
样例输出
14
题目分析：数据量不大，考虑用四维dp，dp[i][j][ma][num]表示到点(i，j)时最大值为ma取得了num个宝贝的方法数，对于某个点如果它的宝藏值大于当前最大值，则我们可以取也可以不取，否则我们只能不取，因此转移方程：
if(ma < val[i][j]) dp[i] [j] [ val[i][j] ] [num + 1] = (dp[i] [j] [ val[i][j] ] [num + 1] + dp[i - 1] [j] [ma] [num] + dp[i] [j - 1] [ma] [num]) % MOD //取
dp[i] [j] [ma] [num] = (dp[i] [j] [ma] [num] + dp[i - 1] [j] [ma] [num] + dp[i] [j - 1] [ma] [num]) % MOD //不取 (这里没有else，因为不论我们能不能取，我们都可以选择不取)，最后我们只要累加dp[n][m][各最大值][k]的值即可，初始dp[1][1][val[1][1]][1] = 1第一个点取，dp[1][1][0][0]第一点不取
这题还有两个坑点，第一：上述转移方程要分成两段写，因为是对1e9+7取模，我们考虑最坏的情况，括号里的数就可能超int。第二：宝物的价值有可能是0，因为初始化为0，因此混淆了空的点和价值为0的点，因此我们让每个宝藏的价值自增1
int dp[55][55][15][15];
int val[55][55];
int main()
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%d", &val[i][j]);
val[i][j] ++;
}
}
memset(dp, 0, sizeof(dp));
dp[1][1][val[1][1]][1] = 1;
dp[1][1][0][0] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(i == 1 && j == 1)
continue;
for(int num = 0; num <= k; num++)
{
for(int ma = 0; ma <= 13; ma++)
{
if(ma < val[i][j])
{
dp[i][j][val[i][j]][num + 1] = (dp[i][j][val[i][j]][num + 1] + dp[i - 1][j][ma][num]) % MOD;
dp[i][j][val[i][j]][num + 1] = (dp[i][j][val[i][j]][num + 1] + dp[i][j - 1][ma][num]) % MOD;
}
dp[i][j][ma][num] = (dp[i][j][ma][num] + dp[i - 1][j][ma][num]) % MOD;
dp[i][j][ma][num] = (dp[i][j][ma][num] + dp[i][j - 1][ma][num]) % MOD;
}
}
}
}
int ans = 0;
for(int i = 0; i < 13; i++)
ans = (ans + dp[n][m][i][k]) % MOD;
printf("%d\n", ans);
}
首先，先来谈第一个问题，写出其状态转移方程，我们要求的解是从原点手握价值最大的宝物v开始经过不同的路径到终点获得K件宝物的路径总数，我们姑且将此状态记为
d(1,1,k(初始为0，还没拿宝贝),-1(此时手上没有宝物，值记为-1))
那么从此状态出发，可以将其转移为如下的决策
这里在补充说明用状态转移方程可以方便将原问题分解成若干个与原问题相同的子问题，且规模变小。
第二个问题，如果仅仅这样的话，必然存在重复计算的问题，为此必须要采取记忆化搜索的方式，对于已经计算过的结点保存其值，就这条题目而言，必须要用一个四维数组保存，因为它的状态跟位置，个数以及当前最大的宝物价值有关。当重复遍历这个结点时，直接传值。
第三个问题，细节决定成败！！
1.类型用long long稳妥，因为即使MOD了，但是如果两个数加起来还有可能超int。
2.我自己做的时候没注意的一个小错误，导致最后始终不对的疏忽。我错误的把r[MAXN][MAXN][15][15]的初始化为了0，这绝对不正确，因为有可能以某种方式走的状态就是无解，就是0，必须将初始值赋为-1。
3.对于有宝物的初始价值为-1，比较好的处理方式是，最后存放是第四维的下标后移一位
4.这里还要注意,k最多是13，不会超过这个值，所以第三维只要14就够了
4 #define MAXN 60
5 #define MOD %1000000007
6 using namespace std;
7 long long r[MAXN][MAXN][15][15];//保存状态
8 long long map[MAXN][MAXN];//初始地图
9 long long m,n,num;
10 long long dfs(long long i,long long j,long long k,long long v)
11 {
12 long long s=0,t;
13 if(r[i][j][k][v+1]!=-1)
14 return r[i][j][k][v+1];
15 if(i==m&&j==n)//到达终点
16 {
17 if(k==num)
18 {
19 r[m][n][k][v+1]=1;
20 return r[m][n][k][v+1];
21 }
22 else if(k==num-1&&map[m][n]>v)
23 {
24 r[m][n][k][v+1]=1;
25 return r[m][n][k][v+1];
26 }
27 else
28 {
29 r[m][n][k][v+1]=0;
30 return r[m][n][k][v+1];
31 }
32 }
33 else
34 {
35 if(map[i][j]>v)
36 {
37 t=map[i][j];
38 if(i+1<=m)
39 s=(s+dfs(i+1,j,k+1,t)MOD+dfs(i+1,j,k,v)MOD)MOD;
40 if(j+1<=n)
41 s=(s+dfs(i,j+1,k+1,t)MOD+dfs(i,j+1,k,v)MOD)MOD;
42 }
43 else
44 {
45 if(i+1<=m)
46 s=(s+dfs(i+1,j,k,v)MOD)MOD;
47 if(j+1<=n)
48 s=(s+dfs(i,j+1,k,v)MOD)MOD;
49 }
50 r[i][j][k][v+1]=s MOD;
51 return r[i][j][k][v+1];
52 }
53 }
54 int main()
55 {
56 // freopen("data.in","r",stdin);
57 // freopen("data.out","w",stdout);
58 memset(r,-1,sizeof(r));
59 long long i,j,p,q;
60 cin>>m>>n>>num;
61 for(i=1;i<=m;i++)
62 for(j=1;j<=n;j++)
63 cin>>map[i][j];
64 dfs(1,1,0,-1);
65 cout<<r[1][1][0][0]<<endl;
66 return 0;
67 }
http://www.zhuangjingyang.com/%E8%93%9D%E6%A1%A5%E6%9D%AF-%E5%9C%B0%E5%AE%AB%E5%8F%96%E5%AE%9D.html
public class Main
{
//定义四维数组 分别表示x,y,num,maxvalue;
private static int[][][][] a = new int[51][51][13][14];
private static int n;
private static int m;
private static int k;
private final static int N = 1000000007;
//输入矩阵
private static int[][] t = new int[51][51];
public static void main(String[] args)
{
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
k = cin.nextInt();
// 赋值数组
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
t[i][j] = cin.nextInt();
}
//将dfs数组值初始化为-1
for(int i=0;i<51;i++)
for(int j=0;j<51;j++)
for(int k=0;k<13;k++)
for(int l=0;l<13;l++)
a[i][j][k][l] = -1;
int res = dfs(0,0,0,-1);
System.out.println(res);
}
public static int dfs(int x,int y,int num,int maxvalue)
{
//如果不为-1了，说明这里的值已经计算过了可以直接返回了。
if(a[x][y][num][maxvalue + 1] != -1)
return a[x][y][num][maxvalue + 1] ;
int res = 0;
//抵达终点,对于最后这个节点，如果是满足条件的节点的话，返回1。
if(x==n-1 && y==m-1)
{
//两种情况，最后一个节点的能拿与不能拿
if( t[x][y] <= maxvalue) // 小于等于，不能拿
{
if(num == k )
res++;
}
//能拿
else
{
//是否满足条件
if(num==k-1 || num==k)
res++;
}
}
//还未到达终点,dfs ,深度先
if(x+1<n)
{
//对于当前节点能不能拿
//能拿
if(t[x][y] > maxvalue )
{
//能拿还要分为是否拿
res+=dfs(x+1,y,num+1,t[x][y]); // 拿
res%=N;
//不拿的
res+= dfs(x+1,y,num,maxvalue);
res%=N;
}
//不能拿
else
{
res+= dfs(x+1,y,num,maxvalue);
res%=N;
}
}
//广度
if(y+1<m)
{
//和深度差不多一样，就是换成广度的搜索了
//判断能不能拿
if(maxvalue < t[x][y])
{
//拿
res+=dfs(x,y+1,num+1,t[x][y]);
res%=N;
//不拿
res+=dfs(x,y+1,num,maxvalue);
res%=N;
}
else
{
res+=dfs(x,y+1,num,maxvalue);
res%=N;
}
}
//返回从该节点起的计数
a[x][y][num][maxvalue + 1] = res;
return a[x][y][num][maxvalue + 1];
}
}
http://mojijs.com/2014/09/157442/index.html
public class 地宫取宝 {
static int m,n,k;
static int count=0;//拥有的方案的数量
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
int[][] digong=new int[n][m];
k=sc.nextInt();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
digong[i][j]=sc.nextInt();
}
}
dsf(digong,0,0,0,0);
print("有"+count+"种行动方案");
long start = System.currentTimeMillis();
long end = System.currentTimeMillis();
print("此程序运行,花费的时间是" + ((end - start) / 1000.0) + "秒.");
}
//参数分别代表地宫数组当前拥有的宝贝数量have,当前所在的所标i/j,当前的单个宝贝的价值最大值
public static void dsf(int[][] digong,int have,int i,int j,int max){
if(i==n-1&&j==m-1)
{
//如果走到了最后一格
if(have==k) count++;
else if(have==k-1&&max<digong[i][j]) count++;
if(count>1000000007)
count=count00000007;
}
else{//四种行走方式
if(i<n-1)
dsf(digong,have,i+1,j,max);//不拿宝贝向下走
if(j<m-1)
dsf(digong,have,i,j+1,max);//不拿宝贝向右走
if(max<digong[i][j]&&i<n-1)
{
dsf(digong,have+1,i+1,j,digong[i][j]);//拿宝贝向下走
}
if(max<digong[i][j]&&j<m-1)
{
dsf(digong,have+1,i,j+1,digong[i][j]);//拿宝贝向右走
}
}
}
