首页 > 代码库 > poj 2385
poj 2385
题目大意:有两颗苹果树,每一秒会有一颗掉落一个苹果(一共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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。