M_sea

洛谷1353 跑步Running
Luogu算法这是一道DP题。设$f[i] [j]$表示第i分钟疲劳度为j的的最大距离。容易转移:$f[i][0]...
扫描右侧二维码阅读全文
23
2017/09

洛谷1353 跑步Running

Luogu

算法

这是一道DP题。

设$f[i] [j]$表示第i分钟疲劳度为j的的最大距离。

容易转移:

$f[i][0]=max\{f[i-j][j]\}$
$f[i][j]=max\{f[i-1][j-1]+d[i]\}$
$f[i][0]=max\{f[i-1][0],f[i][0]\}$

答案即为$f[n] [0]$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int f[10010][510]; //f[i][j]表示第i分钟疲劳值为j的最大距离  
int d[10010];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&d[i]); //输入
    for (int i=1;i<=n;i++) //DP
    {
        for (int j=1;j<=min(i,m);j++) f[i][0]=max(f[i][0],f[i-j][j]); //DP f[i][0]
        f[i][0]=max(f[i][0],f[i-1][0]); //再取max
        for (int j=m;j>=1;j--) f[i][j]=max(f[i][j],f[i-1][j-1]+d[i]); //DP f[i][j]
    }
    printf("%d\n",f[n][0]); //输出
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 12 PM

发表评论