?

?

思路{

　　對于每一列，小鳥或下落，或上升。那我們很容易想到對應的背包問題！

　　按照完全背包的思想更新上升部分，01背包的方法更新下降部分。

　　撞到柱子了(aluba。。。。。。aluba.。。。。。)不慌，只需把它設為不可打即可，

　　處理出最后到達的的柱子亂搞即可。。。。。。

　　還是比較水的。。。。。。

}?

1 #include<map> 2 #include<set> 3 #include<list> 4 #include<deque> 5 #include<cmath> 6 #include<queue> 7 #include<stack> 8 #include<vector> 9 #include<cstdio> 10 #include<complex> 11 #include<cstring> 12 #include<cstdlib> 13 #include<iostream> 14 #include<algorithm> 15 #define maxx 10010 16 using namespace std; 17 struct ZHU{ 18 int pos,h,l; 19 }a[maxx]; 20 int flag,x[maxx],y[maxx]; 21 int f[2][maxx],now,n,m,k,B; 22 bool comp(const ZHU & A,const ZHU & b){return A.pos<b.pos;} 23 int main(){ 24 scanf("%d%d%d",&n,&m,&k); 25 memset(f,127,sizeof(f));flag=f[1][1]; 26 for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]); 27 for(int i=1;i<=k;++i) 28 scanf("%d%d%d",&a[i].pos,&a[i].l,&a[i].h),a[i].pos++; 29 int nowp=1;sort(a+1,a+k+1,comp); 30 if(a[nowp].pos==1)for(int i=a[nowp].l+1;i<a[nowp].h;++i)f[now][i]=0,nowp=2;//初始化 31 else for(int i=1;i<=m;++i)f[now][i]=0; 32 for(int i=2;i<=n+1;++i){ 33 now^=1;for(int j=1;j<=m;++j)f[now][j]=flag; 34 for(int j=1;j<=m-x[i-1];++j) 35 f[now][j+x[i-1]]=min(f[now^1][j]+1,f[now][j+x[i-1]]),//由于滾動數組先01背包更新解 36 f[now][j+x[i-1]]=min(f[now][j]+1,f[now][j+x[i-1]]);//完全背包更新解 37 for(int j=m-x[i-1]+1;j<=m;++j) 38 f[now][m]=min(f[now^1][j]+1,f[now][m]), 39 f[now][m]=min(f[now][j]+1,f[now][m]);//同上，只是到頂了。。。。 40 for(int j=m;j>y[i-1];--j) 41 f[now][j-y[i-1]]=min(f[now][j-y[i-1]],f[now^1][j]);//處理01背包下降的情況 42 if(a[nowp].pos==i){//判斷柱子 43 for(int j=1;j<=m;++j) 44 if(j<=a[nowp].l)f[now][j]=flag; 45 else if(j>=a[nowp].h)f[now][j]=flag; 46 nowp++; 47 } 48 for(int j=1;j<=m;++j)if(f[now][j]!=flag)B=i;//取最優解 49 if(B!=i)cout<<"0 "<<nowp-2,exit(0); 50 }int ans=flag; 51 for(int i=1;i<=m;++i)ans=min(ans,f[now][i]); 52 if(ans!=flag)cout<<"1 "<<ans; 53 return 0; 54 }

?

轉載于:https://www.cnblogs.com/zzmmm/p/7123861.html

總結

以上是生活随笔為你收集整理的[NOIP2014]飞扬的小鸟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。