POJ 3661 Running

本文主要是介绍POJ 3661 Running，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个dp。

/*
POJ: 3661 RUNNING
*/
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;const int MaxN = 10005;
const int MaxM = 505;int dp[MaxN][MaxM];
int n, m;
int dis[MaxN];void solve()
{memset(dp, 0, sizeof(dp));dp[1][1] = dis[1];for(int i = 2; i <= n; i++) {for(int j = 1; i - j >= 0 && j <= m; j++)dp[i][j] = dp[i-1][j-1] + dis[i];dp[i][0] = dp[i-1][0];for(int k = 1; i - k >= k && k <= m; k++)dp[i][0] = max(dp[i][0], dp[i-k][k]);}
}int main()
{//freopen("data.in", "rb", stdin);while(scanf("%d%d", &n, &m) != EOF) {for(int i = 1; i <= n; i++) {scanf("%d", &dis[i]);}solve();     printf("%d\n", dp[n][0]);}return 0;
}

这篇关于POJ 3661 Running的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---