小明在边塞

题目大意

从左上角走到右下角，只能向下或右走。
平面上一些点上有敌军阻拦小明经过（1），若要经过这些有敌军的点，则需花费单位为1的体力值消灭该点上的敌军。同时，在另一些点上有能量药丸（2），经过该点服用能量药丸则可增加单位为1的体力值。
初始体力值为0。
求走完后所剩的最大的体力值。

输入样例

5 5
0 1 1 1 1
0 1 2 1 0
0 2 0 1 1
0 0 2 0 0
0 0 0 0 0 

输出样例

2

数据范围

对于30％的数据，1≤n,m≤10
对于80％的数据，1≤n,m≤100
对于100％的数据，1≤n,m≤500

思路

这道题我们可以用dp来做。
因为题目说明只能向下或向右走，就是说只能从上面或从左边走过来。
那么动态转移方程就很好设了：
$$f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j]$$
（$f[i][j]$为走到点$ij$所剩最大体力值）

代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,f[501][501],a[501][501];
int main()
{
	//freopen("b.in","r",stdin);
	//freopen("b.out","w",stdout);
	memset(f,-127/3,sizeof(f));//处理体力值为负情况
	scanf("%d%d",&n,&m);//读入
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	{
		scanf("%d",&a[i][j]);//读入
		if (a[i][j]==1) a[i][j]=-1;//标记
		else if (a[i][j]==2) a[i][j]=1;//标记
	}
	f[1][0]=0;//赋初值
	f[0][1]=0;//赋初值
	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];//动态转移方程
	printf("%d",f[n][m]);//输出
	//fclose(stdin); 
	//fclose(stdout);
	return 0;
}