Advertisement
saidnagi

Mouse and corns (DP)

Mar 28th, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.49 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long n,m,a[102][102],s[102][102];
  4. void f(int i,int j){
  5.     if(i==n and j==1){
  6.         return;
  7.     }
  8.     if(s[i][j-1]>=s[i+1][j] and j-1>0){
  9.         f(i,j-1);
  10.         cout<<"R";
  11.     }
  12.     else{
  13.         f(i+1,j);
  14.         cout<<"F";
  15.     }
  16. }
  17. int main(){
  18.     cin>>n>>m;
  19.     for(int i=1;i<=n;i++){
  20.         for(int j=1;j<=m;j++){
  21.             cin>>a[i][j];
  22.         }
  23.     }
  24.     for(int i=n;i>0;i--){
  25.         for(int j=1;j<=m;j++){
  26.             s[i][j]=max(s[i+1][j],s[i][j-1])+a[i][j];
  27.         }
  28.     }
  29.     f(1,m);
  30.     cout<<endl;
  31.     return 0;
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement