牛吃草- Mouse and corns EOlymp - 15-白红宇的个人博客

发布日期：2022-02-10 08:11:06 浏览次数：17 分类：技术文章

本文共 923 字，大约阅读时间需要 3 分钟。

DP题，DFS会超时

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define MAX 0x3f3f3f3ftypedef long long ll;using namespace std;int n,m,k;int a[110][110];int dp[110][110];char idx[110][110];int main(){ cin>>n>>m; for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= m ; j ++) cin>>a[i][j]; dp[n][1] = a[n][1]; for(int i = n -1 ; i >= 1; i--){ dp[i][1] = dp[i+1][1] + a[i][1]; idx[i][1] = 'F'; } for(int j = 2 ; j <= m ;j++) { for(int i = n ; i >= 1; i--) { if(i == n) { dp[i][j] = dp[i][j-1] + a[i][j]; idx[i][j] = 'R'; } else{ dp[i][j] = max(dp[i+1][j],dp[i][j-1]) + a[i][j]; if(dp[i+1][j] < dp[i][j-1]) idx[i][j] = 'R'; else idx[i][j] = 'F'; } } } stack
              
               ans;//从终点开始遍历到起点 int i = 1, j = m; while(1) { ans.push(idx[i][j]); if(idx[i][j] == 'R') j--; else i++; if(i == n && j == 1) break; } while(!ans.empty()) { cout<

转载地址：https://blog.csdn.net/qq_43567222/article/details/114791027 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Windows常用快捷键

下一篇：Falling Apples Kattis - apples （详细注释）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章