洛谷P2029跳舞

题目

DP, 用的\(dp[i][j]\)表示\(i\)之前的数选了\(j\)个得到的最大结果，然后状态转移方程应该是

\[if (j \% t == 0)~~dp[i][j] = max(dp[i][j], max(dp[i - 1][j] - S[i], dp[i - 1][j - 1] + S[i] + B[i]) );
\]

\[else~~dp[i][j] = max(dp[i][j], max(dp[i - 1][j] - S[i], dp[i - 1][j - 1] + S[i]) );
\]

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int n, t, maxn;

int S[1001010], B[100010];

int sums[1001001], sumb[101001];

int dp[5001][5001];//dp[i][j]表示前i个数已经连续跳了j次的最大得分, j属于1到t

int main()

{

 	scanf("%d%d", &n, &t);

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

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

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

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

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

		dp[i][0] = dp[i - 1][0] - S[i];//初始化为负的前缀和，因为不选会扣分。

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

 		for (int j = i; j >= 1; j--)

 		{

 			if (j % t == 0)//

 				dp[i][j] = max(dp[i][j], max(dp[i - 1][j] - S[i], dp[i - 1][j - 1] + S[i] + B[i]) ); // [i-1][j]说明i这个位置的数不选。

			else

				dp[i][j] = max(dp[i][j], max(dp[i - 1][j] - S[i], dp[i - 1][j - 1] + S[i])  );

	 	}

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

 		maxn = max(maxn, dp[n][i]);

 	printf("%d", maxn);

 	return 0;

}

巴特西

洛谷P2029跳舞

最新文章

热门文章