接苹果 动态规划法.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

//接苹果 动态规划法
//PKU 2385
/*
输入
12 2
2 2 2 2 1 2 1 1 2 2 2 1

输出
9
*/

#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

int apple[1002];
int f[1002][50];//f[i][j]表示前i个苹果落下时，移动j次接到的苹果数

void print(int num,int cishu,int x)
{
	int i,j;
	for(i=0;i<num;i++)
	{
		for(j=0;j<=cishu;j++)
		{
			printf("%3d",f[i][j]);
		}
		printf("\n");
	}
	cout<<"x="<<x<<endl;
	system("pause");
}

int cal(int num,int cishu)
{
	int x,i,j,max=0;
	for(i=0;i<num;i++)
	{
		for(j=0;j<cishu;j++)
		{
			f[i][j]=0;//初始化
		}
	}
	for(j=1;j<=cishu;j++)
	{
			f[0][j]=1;//只要移动，不管几次，第一个苹果都可以接到
	}
	if(apple[0]==1) f[0][0]=1;//如果不移动，当第一个苹果是第一颗树掉下来，也可接到
	for(i=1;i<num;i++)
		if(apple[i]==1)
			f[i][0]=f[i-1][0]+1;//不移动时，第i个苹果落下的接到情况
		else f[i][0]=f[i-1][0];
	for(i=1;i<num;i++)
	{
		for(j=1;j<=cishu;j++)
		{
			if((j%2==0&&apple[i]==2)||(j%2==1&&apple[i]==1)) x=0;
			//此时移动不会多接苹果
			else x=1;//此时移动能多接苹果
			if(f[i-1][j]>f[i-1][j-1]) f[i][j]=f[i-1][j]+x;
			else f[i][j]=f[i-1][j-1]+x;//动态规划函数
			if(max<f[i][j]) max=f[i][j];
//			print(num,cishu,x);
		}
	}
	return max;
}
int main()
{
	int num,cishu,i;
	scanf("%d%d",&num,&cishu);
	for(i=0;i<num;i++) scanf("%d",&apple[i]);
	cout<<cal(num,cishu)<<endl;
	return 0;
}