洛谷P1941飞扬的小鸟——细节DP

题目：https://www.luogu.org/problemnew/show/P1941

此题主要注意许多细节，详见代码。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,k,up[10005],down[10005],p[10005],l[10005],h[10005],f[10005][1005],wall[10005];

int INF=1e7;

bool vis[10005];

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i=0;i<n;i++)

		scanf("%d%d",&up[i],&down[i]);

	for(int i=1;i<=k;i++)

		scanf("%d%d%d",&p[i],&l[i],&h[i]),wall[p[i]]=i;

	memset(f,11,sizeof f);

	for(int j=1;j<=m;j++)f[0][j]=0;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

		{

//			if(wall[i]&&(j<=l[wall[i]]||j>=h[wall[i]]))continue;//不可部分！

			if(j==m)

				for(int k=0;k<=up[i-1]&&j-k>0;k++)//k=0

				{

					if(!wall[i-1]||(wall[i-1]&&j-k>l[wall[i-1]]&&j-k<h[wall[i-1]]))

						f[i][j]=min(f[i][j],min(f[i-1][j-k]+1,f[i][j-k]+1));

					else f[i][j]=min(f[i][j],f[i][j-k]+1);

				}

			else if(j-up[i-1]>0)

			{

				if(!wall[i-1]||(wall[i-1]&&j-up[i-1]>l[wall[i-1]]&&j-up[i-1]<h[wall[i-1]]))

					f[i][j]=min(f[i][j],min(f[i-1][j-up[i-1]]+1,f[i][j-up[i-1]]+1));

				else f[i][j]=min(f[i][j],f[i][j-up[i-1]]+1);

			}

			//不可又降又升

			if(f[i][j]<INF&&(!wall[i]||(wall[i]&&j>l[wall[i]]&&j<h[wall[i]])))

				vis[i]=1;

		}

		for(int j=1;j<=m;j++)

			if(j+down[i-1]<=m&&

				(!wall[i-1]||(wall[i-1]&&j+down[i-1]>l[wall[i-1]]&&j+down[i-1]<h[wall[i-1]])))

				{

					f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);

					if(f[i][j]<INF&&(!wall[i]||(wall[i]&&j>l[wall[i]]&&j<h[wall[i]])))

						vis[i]=1;

				}

	}

	if(vis[n])

	{

		int mn=INF;

		for(int j=1;j<=m;j++)

			if(f[n][j]<mn)mn=f[n][j];

		printf("1\n%d",mn);

	}

	else

	{

		int nw,ans=0;

		for(int i=n;i>=1;i--)

			if(vis[i])

			{

				nw=i;

				break;

			}

		for(int i=1;i<=nw;i++)

			if(wall[i])ans++;

		printf("0\n%d",ans);

	}

	return 0;

}