POJ 2385 Apple Catching
题意：解题过程：AC代码：
POJ 2385 Apple Catching
题目传送门
题意：
一头牛要接苹果，一共有两棵树，牛刚开始在第一棵树下，每次可以在两棵树之间移动，给出你T秒内下落苹果的树的编号（1或2），问你最多移动K次，能够接到最多的苹果是多少。
解题过程：
比较水的DP，本来想着用一维记录牛当前在什么位置，后来发现并不用，移动的次数K的奇偶就可以反映出牛当前的位置了。f[i][j]表示第i秒，牛移动了j次，能够接到的最多的苹果数量，（i，j）可转移到（i+1，j）或者（i+1，j+1），如果第i+1时刻牛所在的苹果树掉落了苹果，那么相应的f就加1。最终在∀（i∈[1，w]）中取最大的f[T][i]就是答案。
AC代码：
#pragma GCC optimize (3)
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
int T,w;
int pos[
1005];
int f[
1005][
50];
int main() {
scanf(
"%d%d",&T,&w);
for(
int i=
1;i<=T;i++) {
scanf(
"%d",&pos[i]);
}
memset(f,
0,
sizeof f);
if(pos[
1]==
1) {
f[
1][
0]=
1;
f[
1][
1]=
0;
}
else {
f[
1][
0]=
0;
f[
1][
1]=
1;
}
for(
int i=
2;i<=T;i++) {
for(
int j=
0;j<=w;j++) {
if(j==
0) {
f[i][j]=f[i-
1][j]+pos[i]%
2;
}
else {
f[i][j]=max(f[i-
1][j],f[i-
1][j-
1]);
if(j%
2+
1==pos[i])f[i][j]++;
}
}
}
int ans=-
1;
for(
int i=
0;i<=w;i++) {
ans=max(ans,f[T][i]);
}
printf(
"%d\n",ans);
return 0;
}
本人蒟蒻OIer一枚，欢迎加QQ：840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433665.html
相关资源：JAVA上百实例源码以及开源项目
