hdu-1176（dp）

解题思路：用dp做的，dp[i][j]表示在i时刻，j点的最大馅饼。a[i][j]表示在i这个时刻j点同时掉落的馅饼；

每个点除了0和10之外，都有三种状态；

1、没有移动，这样值就为dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i][j]);

2、从左边移动来的，dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i][j]);

3、从右边移动来的，dp[i][j]=max(dp[i][j],dp[i-1][j+1]+a[i][j]);

初始化dp[i][j]=-1;dp[0][5]=0;本身在5这个点；

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#define maxn 100005

using namespace std;

int dp[maxn][12];

int a[maxn][12];

int n;

int main()

{

    int x,t;

    while(scanf("%d",&n)!=EOF)

    {

        if(n==0)

            return 0;

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

        memset(a,0,sizeof(a));

        while(n--)

        {

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

           a[t][x]++;

        }

        int ans=-888;

        dp[0][5]=0;

        for(int i=1;i<=100000;i++)//时间；

        {

            for(int j=0;j<=10;j++)//地点；

            {

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

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

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

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

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

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

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

            }

        }

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

    }

    return 0;

}

巴特西

hdu-1176（dp）

最新文章

热门文章