牛吃草- Mouse and corns EOlymp - 15
发布日期:2022-02-10 08:11:06 浏览次数:7 分类:技术文章

本文共 958 字,大约阅读时间需要 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<
ans.pop();
}
return 0;}

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

上一篇:Windows常用快捷键
下一篇:Falling Apples Kattis - apples (详细注释)

发表评论

最新留言

逛到本站,mark一下
[***.191.171.25]2022年08月19日 21时05分48秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章