洛谷P1353 USACO 跑步 Running

题目

一道入门的dp，首先要先看懂题目要求。

容易得出状态\(dp[i][j]\)定义为i时间疲劳度为j所得到的最大距离

有两个坑点，首先疲劳到0仍然可以继续疲劳。

有第一个方程：

\(dp[i][0]=max(dp[i-1][0],d[i][0])\)

而如果要休息则一定要休息到疲劳值为0才可以停止。

有第二个方程：

\(dp[i][0]=max(dp[i][0], dp[i-j][j])\)意思是i位置疲劳度为0时的最大距离，是i-j位置疲劳值为j时休息j天的最大距离。

而根据题目意思所得到的不休息选择跑步的方程是：

\(dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + d[i])\)

完善完善转移顺序就可得到程序：

#include <bits/stdc++.h>

#define N 1000101

#define int long long

using namespace std;

int n, m, d[N], dp[10031][531];//第n分钟必须休息到0

signed main()

{

// 	freopen("data.in", "r", stdin);

 	scanf("%lld%lld", &n, &m);

 	for (int i = 1; i <= n; i++)

 		scanf("%lld", &d[i]);

 	for (int i = 1; i <= n; i++)

 	{

 		dp[i][0] = max(dp[i - 1][0], dp[i][0]);

 		for (int j = 1; j <= m; j++)

 			dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + d[i]);//不休息

		for (int j = 1; j <= min(m, n); j++)//休息

			dp[i][0] = max(dp[i][0], dp[i - j][j]);//i位置不疲劳的状态的值

 	}

 	for (int i = n; i <= n; i++)

 		printf("%lld ", dp[i][0]);

 	return 0;

}

巴特西

洛谷P1353 USACO 跑步 Running

最新文章

热门文章