POJ 2385 Apple Catching-白红宇

POJ 2385 Apple Catching

阅读量：2125 次

发布时间：2019-04-30

本文共 924 字，大约阅读时间需要 3 分钟。

题意

一共有两个苹果树，每个树会落下苹果，一共会掉下T个苹果，Bessie最初在第一棵树，一共可以移动W次，最多可以接到几个苹果

AC

dp
dp[ i ][ j ]表示第 i 个苹果在移动 j 次可以接到苹果的最大值
dp[ i ][ j ] = max ( dp[ i - 1][ j ], dp[ i - 1][ j - 1 ] ) + 1 ?

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define N 1000015#define P pair
            
             #define ll long long#define mk(a, b) make_pair(a, b)#define mem(a, b) memset(a, b, sizeof(a))using namespace std;int dp[1003][31];int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif int t, w; cin >> t >> w; vector
             
               a(t + 1); for (int i = 1; i <= t; ++i) { cin >> a[i]; } int ans = 0; for (int i = 1; i <= t; ++i) { for (int j = 0; j <= w; ++j) { if (j == 0) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]); if ((j % 2 && a[i] == 2) || (j % 2 == 0 && a[i] == 1)) dp[i][j]++; ans = max(ans, dp[i][j]); } } cout << ans << endl; return 0;}