PROBLEM LINK:
Author: Sibasish Ghosh
Tester: Saytabrat Panda
Editorialist: Sibasish Ghosh
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming, Greedy
PROBLEM:
You are given a N\times M grid that contains at most one monster or at most one herb on each cell (except the top-left and bottom-right cells. They are empty). The witcher has an initial health point of P points. Each time he comes across a monster or a herb, he loses X points or gains Y points respectively. If the total points become 0, the witcher dies. It is also mentioned that every time he makes a move, he can only move one step left or one step down. You have to find the maximum points he can have when he reaches the destination.
QUICK EXPLANATION:
This is similar to the problem Maximum sum path in a Matrix. Have a look at it, and try to solve this problem.
EXPLANATION:
Let dp[i][j] represent the maximum points the witcher can have when he reaches the cell (i,j) starting from the cell (1,1). It is given that the witcher can only move to a cell below it or to the right of it. So it is clearly understood that the cell (i,j) can be reached only from the cell (i-1,j) or the cell (i,j-1). This implies that dp[i][j] somehow depends on dp[i-1][j] and dp[i][j-1]. But how? Try yourself before proceeding any further.
Don't click on this before trying yourself
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
The above relation is greedy and intuitive. Try it on a piece of paper and convince yourself that it works.
Ok. Half of the work is done. Now, coming to the part when the witcher encounters a monster or a herb. It’s simple. After calculating dp[i][j], update it as follows:
- If the cell contains a monster reduce dp[i][j] by X
- If the cell contains a herb increase dp[i][j] by Y
Now, how to handle the case when the health point at a particular cell becomes less than or equal 0? Simple. Just assign dp[i][j] to a very large negative value. This value will represent that it is not possible to reach this particular cell.
I’ll suggest you to try to implement it yourself before moving on to the solutions below.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input1.txt","r",stdin);
// freopen("output1.txt","w",stdout);
ll t=1;
cin>>t;
while(t--)
{
ll n,m,x,y,i,j,p;
cin>>n>>m>>p>>x>>y;
char grid[n+10][m+10];
ll dp[n+10][m+10];
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cin>>grid[i][j];
}
dp[1][1]=p;
for(i=2;i<=n;i++)
{
dp[i][1]=dp[i-1][1];
if(grid[i][1] == '1')
dp[i][1]-=x;
if(dp[i][1] <= 0)
dp[i][1]=-1e18;
if(grid[i][1] == '2')
dp[i][1]+=y;
}
for(j=2;j<=m;j++)
{
dp[1][j]=dp[1][j-1];
if(grid[1][j] == '1')
dp[1][j]-=x;
if(dp[1][j] <= 0)
dp[1][j]=-1e18;
if(grid[1][j] == '2')
dp[1][j]+=y;
}
for(i=2;i<=n;i++)
{
for(j=2;j<=m;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(grid[i][j] == '1')
dp[i][j]-=x;
if(dp[i][j] <= 0)
dp[i][j]=-1e18;
if(grid[i][j] == '2')
dp[i][j]+=y;
}
}
if(dp[n][m] > 0)
cout<<dp[n][m]<<"\n";
else cout<<"-1\n";
}
return 0;
}
Tester's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
static int n,m;
static long res,p,x,y,dp[][],val;
public static void process()throws IOException
{
n=ni();m=ni();
p=nl();x=nl();y=nl();res=-1l;
dp=new long[n+2][m+2];
for(long row[] :dp)
Arrays.fill(row,0l);
char grid[][]=new char[n+1][];
for(int i=1;i<=n;i++)
grid[i]=(" "+nln()).toCharArray();
dp[1][1]=p;
for(int i=2;i<=n;i++){
dp[i][1]=dp[i-1][1];
if(dp[i][1]==0)
continue;
if(grid[i][1]=='1')
dp[i][1]-=x;
else if(grid[i][1]=='2')
dp[i][1]+=y;
dp[i][1]=(dp[i][1]<=0)?0l:dp[i][1];
}
for(int i=2;i<=m;i++){
dp[1][i]=dp[1][i-1];
if(dp[1][i]==0)
continue;
if(grid[1][i]=='1')
dp[1][i]-=x;
else if(grid[1][i]=='2')
dp[1][i]+=y;
dp[1][i]=(dp[1][i]<=0)?0l:dp[1][i];
}
for(int i=2;i<=n;i++){
for(int j=2;j<=m;j++){
long take=Math.max(dp[i-1][j], dp[i][j-1]);
if(take==0)
continue;
if(grid[i][j]=='1')
take-=x;
else if(grid[i][j]=='2')
take+=y;
if(take<=0)
continue;
dp[i][j]=take;
}
}
//print_arr();
pn(dp[n][m]>0?dp[n][m]:-1);
}
static void print_arr(){
for(long row[] : dp)
pn(Arrays.toString(row));
}
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
out = new PrintWriter(System.out);
sc=new AnotherReader();
boolean oj = true;
//oj = System.getProperty("ONLINE_JUDGE") != null;
if(!oj) sc=new AnotherReader(100);
long s = System.currentTimeMillis();
int t=1;
t=ni();
while(t-->0)
process();
out.flush();
if(!oj)
System.out.println(System.currentTimeMillis()-s+"ms");
System.out.close();
}
static void pn(Object o){out.println(o);}
static int ni()throws IOException{return sc.nextInt();}
static String nln()throws IOException{return sc.nextLine();}
static long nl()throws IOException{return sc.nextLong();}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
Feel free to write your approach in the comments 
