Description
有一块地被划分成了n*m个区域，在一些区域里有垃圾要拾捡。
现在科研人员开发了一个能捡垃圾的机器人，机器人每一次都可以移动一个区域的距离。
假设机器人从最左上区域出发，他每次只能向右或者向下走。
每次他到达一个点，就会自动把这个点内的垃圾拾掉。
问：该机器人最多能够拾多少垃圾？
在最多情况下，有多少种方案？
Input
输入文件的第一行为两个整数n和m；
接下来有一个n*m的01矩阵。
矩阵中的第i行j列的数字a[i][j]=0表示为空地。
a[i][j]=1表示为垃圾。
Output
输出两行，第一行为一个数字表示最多拾到的垃圾，第二行为一个数字表示在最多情况下，有多少种方案。
Sample Input
3 3
100
000
010
Sample Output
2
3
今天也是菜得水3级题的一天呢
因为机器人只能向下和向右走，满足无后效性。
所以我们考虑用DP作答。
首先，从输入上就有那么一个小小的坑就只有我觉得是坑吧，请大家研究一下矩阵的输入。
科科，是没有空格的。
所以我们要用string或者char数组来读入~
接着分析题意。
对于题目中的人工智障机器人，它到一个点的路径只有两
种：从上来或者从左来。
也就是说，对于题目中的点a[i][j]，它只可能源于点a[i-1][j]与点a[i][j-1]。
这点理清了，下面就可以顺理成章地理解了。
一：求最多捡到的垃圾
我们可以用f[i][j]来统计捡到的最多垃圾数。由加法原理得出，f[i][j]=f[i-1][j]+f[i][j-1]。
实现代码：
//DP求最多拾到的垃圾
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
这样下来，f[n][m]就是到达终点时捡到的最多垃圾数。即我们要的答案。
二：求在最多情况下，有多少种方案？
我们可以用q[i][j]来统计f最大时的方案数。
可得**有q[i][j]=q[i-1][j]C1+q[i][j-1]C2。
其中，若f[i-1][j]+a[i][j]==f[i][j]，则C1=1，反之为0；
若f[i][j-1]+a[i][j]==f[i][j]，则C2=1，反之为0；
但是这样做还有一个问题：边界值的问题。
对于矩阵来说，最上和最右的点，是一定可以到达的。所以，我们可以把它们的初值赋为1。
这样一来，我们的计算式子不仅有了初始值，还没有了越界的漏洞。
实现代码：
//DP求路径数
for(int i=1;i<=n;i++)
{
q[1][i]=1;
q[i][1]=1;
}
//边界赋初值
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
{
long long C1,C2;
if(f[i-1][j]+a[i][j]==f[i][j])
C1=1;
else C1=0;
if(f[i][j-1]+a[i][j]==f[i][j])
C2=1;
else C2=0;
q[i][j]+=q[i-1][j]*C1+q[i][j-1]*C2;
}
似乎 一切都功德圆满了。
等等，你有看到窝的加粗嘛？
当初自信的可怜的continue就是这样WA的。。。。
在一群乐于助蒻的大佬指导下，窝当时整个人就一懵的。
没错，本题最重要的部分不在前面。
其实，最重要的是
开 long long 。 。 。 。 。
惊不惊喜？
完整代码：
#include <iostream>
#include <string>
#define maxn 105
using namespace std;
string s[maxn];
long long a[maxn][maxn]; //a数组表示矩阵
long long f[maxn][maxn]; //f数组表示当前捡的最多垃圾数
long long q[maxn][maxn]; //g数组表示f最大时的方案数
int main()
{
long long n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=1;j<=m;j++)
a[i][j]=s[i][j-1]-'0';
}
//DP求最多拾到的垃圾
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
cout<<f[n][m]<<endl;
//DP求路径数
for(int i=1;i<=n;i++)
{
q[1][i]=1;
q[i][1]=1;
}
//边界赋初值
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
{
long long C1,C2;
if(f[i-1][j]+a[i][j]==f[i][j])
C1=1;
else C1=0;
if(f[i][j-1]+a[i][j]==f[i][j])
C2=1;
else C2=0;
q[i][j]+=q[i-1][j]*C1+q[i][j-1]*C2;
}
cout<<q[n][m]<<endl;
return 0;
}
QAQ求点赞
前往洛谷博客体验更佳：传送门