首页 > 代码库 > poj 2385

poj 2385

2024-07-08 07:17:22   219人阅读

题目大意:有两颗苹果树，每一秒会有一颗掉落一个苹果(一共n秒)，问在限制最多转换(从一颗走到另一颗)m次下最多能得到多少苹果。

分析：

dp[i][j][k]表示第i秒转换了j次当前在第k棵树下得到的苹果数最大值

显然只与上一秒的状态有关

dp[i][j][k]=max{dp[i-1][j][k],dp[i-1][j-1][1-k]}+a[i][k] {a[i][k]表示第i秒第k棵树是否有苹果}

那么答案就是max{dp[n][j][k]}

空间上可以优化，可以把第一维拿掉只要保证i是从小到大枚举的

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<vector> 9 #include <cmath>10 #define maxn 101011 #define maxm 100000012 #define mod  100000000013 #define INF 0x3f3f3f3f14 using namespace std;15 int dp[maxn][40][2];16 int n,m;17 int a[maxn][2];18 int main (){19     while(cin>>n>>m){20         for(int i=1;i<=n;++i){21             int x;22             cin>>x;23             a[i][x-1]=1;24             a[i][2-x]=0;25         }26         dp[0][0][0]=0;27         dp[0][0][1]=0;28         for(int i=1;i<=n;++i){29             dp[i][0][0]=dp[i-1][0][0]+a[i][0];30             dp[i][0][1]=dp[i-1][0][1]+a[i][1];31         }32         for(int i=1;i<=n;++i){33             for(int j=1;j<=m;++j){34                 dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1])+a[i][0];35                 dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0])+a[i][1];36             }37         }38         int ans=0;39         for(int i=0;i<=m;++i){40             for(int j=0;j<2;++j){41                 ans = max(ans,dp[n][i][j]);42             }43         }44         cout<<ans<<endl;45     }46 }
View Code

 


联系
我们