#include<cstdio>
#include<iostream>
using namespace std;
int a[1005],dp[10005][35];//dp[i][j],i分钟时用了j次移动后得到的苹果数目 
int main()
{
	int i,j,n,m,t,Max = 0;
	scanf("%d %d",&n,&m);
	for(i = 1;i <= n;i ++)
		scanf("%d",&a[i]);
	for(i = 1;i <= n;i ++)
	{
		dp[i][0] = dp[i-1][0] + 2 - a[i];//只要是移动0次，则一定在苹果树1的位置 
		for(j = 1;j <= m;j ++)//若j为奇数则在苹果树2位置，否则在1位置 
		{
			/*之所以现在移动步数为j，是从j-1步移动过来的，或者是和上一步一样没有动*/
			if(j % 2)
				dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + a[i] - 1;
			else
				dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + 2 - a[i];
		}
	}
	for(i = 0;i <= m;i ++)
		Max = max(Max,dp[n][i]);
	printf("%d\n",Max);
	return 0;
}

• Re:路过 (0) Jason_zjj 2015-04-20 21:49:46
• Re:贴代码，还是挺水的 (706) 827695609 2018-04-16 15:46:19
• Re:贴代码，还是挺水的 (9) HrbustKunKun 2022-01-11 16:18:43
  • Re:谢谢，加强理解 (11) HrbustKunKun 2022-01-11 16:19:29