首页 > 其他 > 详细

P1353 [USACO08JAN]跑步Running

时间:2018-07-22 19:13:32      阅读:204      评论:0      收藏:0      [点我收藏+]

递推更新的就是坑。。。


\(dp[i][j]\)为第\(i\)分钟,疲劳度为\(j\)的最大跑步距离。

发现了一种叫做“刷表法”的东西。我虽然不知道是什么东西,但是第一次写的时候就是用这种思想。

刷表法就是用已知的信息来更新后面的信息。而想记忆化搜索、普通递推的,叫做填表法。

下面是更新的方法:

你可以休息,连你疲劳度为0也可以。\(dp[i + 1][0] = max(dp[i + 1][0], dp[i][0])\)

疲劳度不为0的时候,设为\(j\),显然需要\(j\)天才休息好。\(dp[i + j][0] = max(dp[i + j][0], dp[i][j])\)

你可以跑步。\(dp[i + 1][j + 1] = dp[i][j] + d[i + 1]\)(这里注意是\(d[i + 1]\),因为你更新的是\(i +1\)天的状态)

你疲劳度为m的时候就不能继续跑了,所以上面注意。

坑点

  • 你数组不要只开大5个。不然RE。

  • 即使你最终答案是\(dp[n][0]\),你\(i\)也要取\(n\)

  • 你需要先讨论休息,后讨论跑步。

代码:

#include<cstdio>
#include<algorithm>
const int maxn = 10505, maxm = 505;
int dp[maxn][maxm];
int d[maxn];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &d[i]);
    dp[1][0] = 0; dp[1][1] = d[1];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            if(j) dp[i + j][0] = std::max(dp[i + j][0], dp[i][j]);
            else dp[i + 1][0] = std::max(dp[i + 1][0], dp[i][0]);
            if(j != m) dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i][j] + d[i + 1]);
        }
    }
    printf("%d\n", dp[n][0]);
    return 0;
}

P1353 [USACO08JAN]跑步Running

原文:https://www.cnblogs.com/Garen-Wang/p/9350972.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!