题意：
一开始你在树1下，你可以在树之间来回移动w次，每秒在某棵树下会掉落苹果，你在树下你就能得到，问，t时间内可以得到最多多少苹果；
解题思路：
dp[i][j]代表i时刻你移动了j次所得到的苹果
那么dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])表示在上一秒你移动或不移动得到的最大值再加上：
如果这一秒你站在掉苹果的树下，那么这一秒你可以得到一个苹果，dp[i][j] ++ ;
AC代码：
#include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define maxn 1010 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(x,y) memset(x,y,sizeof(x)) #define rep(i,n) for(int i=0;i<(n);i++) #define repf(i,a,b) for(int i=(a);i<=(b);i++) #define pii pair<int,int> //#define mp make_pair #define FI first #define SE second #define IT iterator #define PB push_back #define Times 10 typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int ,int > P; const double eps = 1e-10; const double pi = acos(-1.0); const ll mod = 1e9+7; const int inf = 0x3f3f3f3f; const ll INF = (ll)1e18+300; const int maxd = 1000500 + 10; int dp[1010][1010]; int ac[1010]; int main() { int t, w; cin >> t >> w; for (int i = 1; i <= t; i ++) { cin >> ac[i]; } ms(dp, 0); if(ac[1] == 1) dp[1][0] = 1; if(ac[1] == 2) dp[1][1] = 1; for (int i = 2; i <= t; i ++) { for (int j = 0; j <= w; j++) { if(j == 0) { dp[i][j] = dp[i - 1][0]; if(ac[i] == 1) { dp[i][j] ++; } continue; } dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]); if(j%2 + 1== ac[i]) { dp[i][j] ++; } } } int ans = 0; for (int i = 0; i <= w; i++) { ans = max(ans, dp[t][i]); } cout << ans << endl; }