题意：给出一个矩阵的长和宽n，m，然后输入一些坐标，表示那个坐标上有垃圾（这道题里面每个坐标只有一个垃圾），然后机器人从(1,1)开始运动终点是(n,m)
运动的方向只能是向下或者向右走，途中它要捡垃圾，目的是要令它捡的垃圾数最多，然后在能保证捡到的垃圾数最多的情况下，统计出有多少种方法，然后输出其中任意的一种方案。另外，这里面要给所有的格子编号，从第1行开始从左往右编号1,2,3……然后接着下一行，所以所有的编号分别是1,2,3……n*m。我们在输出任意的一种 方案时，是按照捡垃圾的顺序输出垃圾所在坐标的编号。另外怎么为之不同的方案，是指垃圾的编号不同，例如题中的例子
<2, 4, 11, 13, 28>
<2, 4, 11, 13, 41>
<2, 4, 11, 25, 28>
<2, 4, 11, 25, 41>
都是有5个垃圾，每个垃圾都有编号，只要有一个编号不同视为一个方案
思路：要求最大值即最多捡到多少个垃圾这个问题很容易想到，要记录最后的任意一种方案也不难，难在统计一共有多少方案数，一开始我是将三者合并在一个记忆化搜索中企图实现它，但是一直无法做到，然后上网查了其他思路很多人都说转化为LIS问题求解，我略看一下大体思路能理解，但是我已经写了记忆化搜索，还是希望能用记忆化搜索去实现，最后还是想到了方法
DP(记忆化搜索实现)：num[i][j]=max { num[i+1][j] , num[i][j+1]}+g[i][j] , 其中g[i][j]是记录坐标(i,j)处是否有垃圾，所以g[i][j]的值只有0或1，这状态转移方程的意思是，num[i][j]表示从坐标（i，j）出发能捡到的最多的垃圾，那么它下一步可以向左走到(i,j+1)或者向下走到（i+1,j），另外如果它本身的位置上就有垃圾那么就要+1，否则不变，而g[i][j]只有0,1而且就是表示有无垃圾那么就直接+g[i][j]
而path[s]数组是记录路径，但确定了下一步要走的方向后，就可以记录下一个的坐标，但是坐标有两个值，而题目刚好是要输出编号而不是坐标的，所以就干脆转化为编号，其实path[s]中的s是当前位置(i,j)转化为编号后的值,而它的值就是它下一步要到达的坐标转化后的编号
我们输出路径的时候就是从path[1]开始（编号1开始），然后递归到它的下一个编号。没到一个编号，先转化为坐标，然后判断g[i][j]是否为1，若为1，说明这个坐标下有垃圾，要输出这个编号，如果为0，那么说明这个只是路径上的一个点但是没有垃圾，注意我们最后只需要输出路径中有垃圾的编号，没垃圾的编号不需要输出
最后就是统计有多少方案数的问题，这个问题要另外用一个记忆化搜索去实现
count[i][j]表示位于坐标（i，j）时要捡到num[i][j]个垃圾的方案说（之前的记忆化搜索已经结束，此时num[i][j]保存的已经是最优解，也就是要达到这个最优解有多少方案）
我们来到当前下标(i,j)，那么我们有可能到达它的右下方的所有点(即这个点和整个矩形的右下角的点连成对角线的那个小矩形里面所有的点我们都是有可能到达的。)，那么我们就去枚举所有的这些点，然后然这些点中那些是有垃圾的，如果有垃圾，我们又看在num数组方面两者是否存在关系.
比如我们枚举的点的坐标为(x,y)，如果g[x][y]=1（有垃圾）,而且num[i][j]=num[x][y]+g[i][j](即从(i,j)出发的话要想得到最优解必定会经过(x,y)，因为它们在最优解上存在着直接的递推关系)那么count[i][j]+=count[x][y],加上(x,y)坐标下的方案数
看代码
#include <stdio.h> #include <string.h> #define MAX 110 #define M 10100 bool g[MAX][MAX]; int num[MAX][MAX],path[M]; long long count[MAX][MAX]; bool visit[MAX][MAX]; int n,m; /* //仅供测试输入 void print_input() { int i,j; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) printf("%d ",g[i][j]); printf("\n"); } printf("*******************\n"); return ; }
*/ int input() { int x,y; scanf("%d%d",&n,&m); if(n==-1 && m==-1) return 0; while(1) { scanf("%d%d",&x,&y); if(!x && !y) break; g[x][y]=1; } return 1; } void dp(int i , int j) { int n1,n2; long long c1,c2; int p1,p2,p3; if(visit[i][j]) return ; visit[i][j]=1; num[i][j]=0; if(g[i][j]) num[i][j]++; n1=n2=c1=c2=0; //向左递归 if(j<=m-1) { dp(i,j+1); n1=num[i][j+1]; } //向下递归 if(i<=n-1) { dp(i+1,j); n2=num[i+1][j]; } p1=(i-1)*m+j; p2=(i-1)*m+j+1; p3=i*m+j; if(n1>n2) //向左做递归消去的垃圾数更多 { num[i][j]+=n1; path[p1]=p2; } else if(n1<n2) { num[i][j]+=n2; path[p1]=p3; } else { num[i][j]+=n1; path[p1]=p2; } return ; } void print_path(int s , int c) { int x,y,next; // if(s==n*m) return ; if(c>num[1][1]) return ; //已经全部输出完毕了
//将编号转化为坐标,然后看这个坐标有没有垃圾 if((s%m)==0) { y=m; x=s/m;} else { y=s%m; x=(s/m)+1; } next=path[s]; if(g[x][y]) { if(c==num[1][1]) printf("%d\n",s); else printf("%d ",s); print_path(next,c+1); } else print_path(next,c); return ; } long long way(int i, int j) { int dx,dy; if(visit[i][j]) return count[i][j]; visit[i][j]=1; count[i][j]=0; if(num[i][j]==1) return count[i][j]=1; //如果最大垃圾数为1，那么方案数也没1，因为方案数不是指路径有多少种可能，而是仅仅是看有垃圾的编号
for(dx=0; i+dx<=n; dx++) for(dy=0; j+dy<=m; dy++) { if(!dx && !dy) continue; if( g[i+dx][j+dy] && num[i][j]==num[i+dx][j+dy]+g[i][j]) count[i][j]+=way(i+dx , j+dy ); } return count[i][j]; } void solve(int T) { int i; memset(visit,0,sizeof(visit)); dp(1,1); memset(visit,0,sizeof(visit)); way(1,1); printf("CASE#%d: ",T); printf("%d %lld ",num[1][1],count[1][1]); print_path(1,1); return ; } int main() { int T=0; while(1) { memset(g,0,sizeof(g)); if(!input()) break; // print_input(); T++; solve(T); } return 0; }