[01背包]【NOIP2014D1T3】飛揚的小鳥 題解

寫在前面：

所有背包類的DP我都最後寫成01背包了……已經習慣這麼用，3年了……

是以看到小标題寫01背包别吃鲸

洛谷傳送門在此

UOJ傳送門在此

解題分析

不得不說這道題對付我這個PJ組水準蒟蒻還是很有用的。

O ( n m 2 ) O(nm^2) O(nm2)的思路比較簡單： f [ i ] [ j ] f[i][j] f[i][j]表示走到第i列第j行至少需要走幾步，僞代碼如下

for i= 1 ~ n 
    for j= 1 ~ m 
    {
      f[i][j]=f[i-1][j+b[i-1]]
      for k 1 to (m-j)/a[i-1] f[i][j]=min(f[i][j],f[i-1][j-k*a[i-1]]+k)
     }
           

不過這個複雜度實在不敢恭維，70分有了，100分？做夢！

等一下，那個 ( m − j ) / a [ i − 1 ] (m-j)/a[i-1] (m−j)/a[i−1]有點眼熟，根據題目可以想一下，這個點選次數理論上是無限的（盡管由于要少點幾下不會怎麼做），然後記憶裡回想一下，這個方程是不是有點眼熟，這個模型……

好吧，這模型就是完全背包啊（不是我自己想出來的），是以可以分開處理向上和向下，向上的部分完全背包解決，然後專門處理 f [ i ] [ m ] f[i][m] f[i][m]（快接近頂部，再點一下就到頂部了），然後專門處理向下（這又是個01背包），水管部分最後再刷成INF。轉移方程見代碼

####複雜度

時間： O ( n m ) O(nm) O(nm)

空間： O ( n m ) O(nm) O(nm)，重金求子一維或滾動數組解決的~~，價格私信聊~~_

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k,INF,ans,cnt,f[10005][1005],a[10005],b[10005],L[10005],R[10005];
inline void readi(int &x){
	x=0; char ch=getchar();
	while ('0'>ch||ch>'9') ch=getchar();
	while ('0'<=ch&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
}
void _init(){
	freopen("bird.in","r",stdin);
	freopen("bird.out","w",stdout);
	readi(n); readi(m); readi(k);
	memset(f,63,sizeof(f)); INF=f[0][0];
	for (int i=1;i<=m;i++) f[0][i]=0;
	for (int i=0;i<n;i++){
		readi(a[i]); readi(b[i]);
		L[i+1]=0; R[i+1]=m+1;
	}
	for (int i=1,x,y,z;i<=k;i++){
		readi(x); readi(y); readi(z);
		L[x]=y; R[x]=z;
	}
}
void _solve(){
	cnt=0; ans=INF;
	for (int i=1;i<=n;i++){
		for (int j=a[i-1]+1;j<=m;j++)
			f[i][j]=min(f[i-1][j-a[i-1]],f[i][j-a[i-1]])+1;
		for (int j=m-a[i-1];j<=m;j++)
        	f[i][m]=min(f[i][m],min(f[i-1][j],f[i][j])+1);
		for (int j=1;j<=m-b[i-1];j++)
			f[i][j]=min(f[i][j],f[i-1][j+b[i-1]]);
		for (int j=1;j<=L[i];j++) f[i][j]=INF;
		for (int j=R[i];j<=m;j++) f[i][j]=INF;
		bool pd=1;
		for (int j=L[i]+1;j<R[i];j++)
			if (f[i][j]<INF)  {pd=0; break;}
		if (pd) {printf("0\n%d",cnt); return;}
		if (L[i]!=0||R[i]!=m+1) cnt++;
	}
	for (int i=1;i<=m;i++) ans=min(ans,f[n][i]);
	printf("1\n%d",ans);
}
int main()
{
	_init();
	_solve();
	return 0;
}