Problem C:
   简单DP  f[i][0]表示第偶数次到i，f[i][1]表示第奇数次到i
   f[i][0]=max(f[j][1])-a[i]  1<=j<i
   f[i][1]=max(f[j][0])+a[i]  1<=j<i

考虑不走这格的情况f[i][0]=f[i-1][0]  假设能这么走，显然不影响答案而少枚一维

由于偶数扣分 所以最后走的一定是单步

答案为f[n][1]

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (30000+10)
int n,a[MAXN],f[MAXN][2]={0};
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i][1]=a[i];
	}
	for (int i=1;i<=n;i++)
	{
		f[i][1]=max(max(f[i][1],f[i-1][1]),f[i-1][0]+a[i] );

		f[i][0]=max(max(f[i][0],f[i-1][0]),f[i-1][1]-a[i]);
	}
/*	for (int i=1;i<=n;i++) cout<<f[i][1]<<' ';
	cout<<endl;
	for (int i=1;i<=n;i++) cout<<f[i][0]<<' ';
	cout<<endl;

*/
/*
	int ans=f[1][1];
	for (int i=2;i<=n;i++) ans=max(ans,max(f[i][1],f[i][0]));
	cout<<ans<<endl;
*/
	cout<<f[n][1]<<endl;

	return 0;
}

第三题  草草草（grass）

问题描述：

    有N棵小草，编号0至N-1。乐滋滋巨神不喜欢小草，所以乐滋滋要剪草，使得N棵小草的高度总和不超过H。在第0时刻，第i棵小草的高度是h[i]，接下来的每个整数时刻，会依次发生如下三个步骤：

（1）每棵小草都长高了，第i棵小草长高的高度是grow[i]。

（2）乐滋滋选择其中一棵小草并把它剪平，这棵小草高度变为0。注意：这棵小草并没有死掉，它下一秒还会生长的。

（3）乐滋滋计算一下这N棵小草的高度总和，如果不超过H，则完成任务，一切结束，    否则轮到下一时刻。

你的任务是计算：最早是第几时刻，乐滋滋能完成他的任务？如果第0时刻就可以完成就输出0，如果永远不可能完成，输出-1，否则输出一个最早的完成时刻。

输入格式：

第一行，两个整数N和H。 1 ≤ N ≤ 50，0 ≤ H ≤ 1000000。

第二行，N个整数，表示h[i]。0 ≤ h[i] ≤ 100000。

第三行，N个整数，表示grow[i]。1 ≤ grow[i] ≤ 100000。

    对于20%的数据， 1 ≤ N
≤ 7。

输出格式：

  一个整数，最早完成时刻或-1。

输入输出样例：

本体是背包+贪心

由于值会变，需要对物品选取的先后顺序排序

毫无疑问   一棵草不可能✄两次 否则无解

另外，如果最后砍得草是已知的（对应题中N=最早时刻），那这题肯定是最后砍长得快的

进而衍生，倘若最后砍的草是确定的，先砍长得慢的

我们用w(i) 表示第i时刻的价值，显然不砍的话，它是单调递增的（grow[i]>0)

所以我们在砍长得第i慢的草时，只有长速为1~i-1 的草有可能被砍，后面的草一定不会砍的

所以它的状态可以由前（i-1)棵草 得到，有单调子结构，可以Dp背包

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXH (1000000+10)
#define MAXN (50+10)
struct grass
{
	int h,g;
	friend bool operator<(const grass a,const grass b){return a.g<b.g;} //先割长得慢的，后割快的
    int w(const int i){return h+i*g;}
}a[MAXN];
int n,H,f[MAXN][MAXN];  //f[i][j]表示 到第i棵 且 取了 j 棵
bool is_ok(int m)
{
	memset(f,0,sizeof(f));

	for (int i=1;i<=n;i++)
		for (int j=1;j<=min(i,m);j++)
		{
			f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i].w(j));		//如果到第i次时割j稞最优值 就是0/1背包
		}
	int ans=0;
	for (int i=1;i<=n;i++) ans+=a[i].w(m);
	if (ans-f[n][m]<=H)
	{
		cout<<m<<endl;
//		while (1);
		exit(0);
	}


	return 0;
}
int main()
{
	freopen("grass.in","r",stdin);
	freopen("grass.out","w",stdout);
	scanf("%d%d",&n,&H);
	for (int i=1;i<=n;i++) cin>>a[i].h;
	for (int i=1;i<=n;i++) cin>>a[i].g;
	sort(a+1,a+1+n);
	for (int i=0;i<=n;i++) is_ok(i);
	cout<<"-1n";





//	while (1);
	return 0;
}