HDU1176(正推DP)

时间和位置都可以决定这一秒捡到的馅饼数

不妨设\(dp[i][j]\)为在\(i\)秒\(j\)位置的最大收益

那么\(dp[0][5]=0\),dp数组的其他部分置成-1代表不能转移

那么对于第\(i\)秒，可以从第\(i-1\)秒的j,j-1,j+1位置转移而来

代码也呼之欲出了

#include <iostream>

#include <cstring>

#include <cstdio>

#include <math.h>

using namespace std;

const int maxn=100009;

int n,vis[maxn][13],dp[maxn][13];

int main()

{

	while(cin>>n&&n)

	{

		int ans=0,x,y,da=0;

		memset(vis,0,sizeof(vis));

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

		{

			scanf("%d%d",&x,&y);

			vis[y][x]++;//y秒有x个饼

			da=max(da,y);

		}

		memset(dp,-1,sizeof(dp));

		dp[0][5]=0;

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

		{

			for(int j=0;j<=10;j++)

			{

				if(j!=10&&dp[i-1][j+1]!=-1)

					dp[i][j]=max(dp[i][j],dp[i-1][j+1]+vis[i][j]);

				if(dp[i-1][j]!=-1)

					dp[i][j]=max(dp[i][j],dp[i-1][j]+vis[i][j]);

				if(j!=0&&dp[i-1][j-1]!=-1)

					dp[i][j]=max(dp[i][j],dp[i-1][j-1]+vis[i][j]);

				ans=max(ans,dp[i][j]);

			}

		}

		cout<<ans<<endl;

	}

}

巴特西

HDU1176(正推DP)

最新文章

热门文章