首页 > 代码库 > poj 2385
poj 2385
第一次完全靠自己写出dp,比较激动,让我安静会,,,虽然比较简单。这个题就是分情况讨论就行,我是先通过来回次数考虑位置,然后考虑是否这个位置有苹果落下
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=1000+10; int a[maxn]; int d[maxn][50]; int n,t; int main() { while(~scanf("%d%d",&n,&t)) { for(int i=1; i<=n; i++) scanf("%d",&a[i]); memset(d,0,sizeof(d)); for(int i=1; i<=n; i++) { int zz=min(i,t); for(int j=0; j<=zz; j++) { if(j%2==0)//现在在第一棵树 { int m1; if(a[i]==1)//第一棵树落苹果 m1=d[i-1][j]+1;//在树下不动 else m1=d[i-1][j]; int m2; if(j-1>=0) m2=d[i-1][j-1]+1;//从另一棵树跑过来 else m2=0; d[i][j]=max(m1,m2); } else if(j%2==1)//在第二颗树 {//同上 int m1; if(a[i]==2) m1=d[i-1][j]+1; else m1=d[i-1][j]; int m2; if(j-1>=0) m2=d[i-1][j-1]+1; else m2=0; d[i][j]=max(m1,m2); } } } int mm=0; for(int i=0;i<=t;i++) mm=max(mm,d[n][i]); printf("%d\n",mm); } return 0; }
poj 2385
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。