【NYNU 1151】轻羽飞扬数塔DP

原题地址：http://47.93.252.151/problem.php?id=1151

1151: 轻羽飞扬

题目描述

电视动画《轻羽飞扬》改编自滨田浩辅原作的同名漫画，作为今年的7月新番，dyl非常喜欢尤其是里面的大魔王&&主角羽咲绫乃，我们知道绫乃小的时候特别喜欢打羽毛球，她的母亲千夏是一个非常有名的羽毛球选手曾获得女子单人羽毛球全日本综合优胜十连霸冠军，对待自己的女儿千夏有独特的训练方式，绫乃很喜欢和母亲打羽毛球，但是呢千夏每天只和绫乃打一局，一旦绫乃接不住母亲的球，千夏就让绫乃自己训练，作为绫乃的好朋友藤泽英玲奈你将如何帮助绫乃能够更多的接到母亲的羽毛球呢？

首先我们将羽毛球场分成0-10 11个位置如图所示

最开始绫乃站在5的位置，每一秒钟都会有若干个球落在若干个位置，由于绫乃刚刚进行过训练所以很累，她只能接到所处位置或者相邻位置上的球，所以绫乃最多能够接到几个球呢？

输入

输入有多组不超过10组数据以0结尾

每组第一行一个数 n 表示球的数量 (n<100000)

第二行到n+1行每行两个数x,t （x代表球落下的位置，t代表第几秒） (t<100000)

输出

一个数代表绫乃最多能够接到的球的数量

开始时站在5这个位置，因此在第一秒，ta只能接到4,5,6这三个位置中其中一个位置上的羽毛球。问最多可能接到多少个球？

样例输入

样例输出

第一次写的时候用DFS爆搜，完美地码了出来，十分激动，然后完美地TLE了。。。

TLE的代码：（时间超限 83%）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
 
int a[12][1000005];
int te,ans;
 
void dfs(int n,int time,int sum)
{
    int i,tmp=0;
    tmp=sum+a[n][time];
    ans=max(ans,tmp);
    if(time==te)
        return ;
    for(i=-1;i<=1;i++)
    {
        if(n+i<0||n+i>11)
            continue;
        dfs(n+i,time+1,tmp);
    }
}
 
int main()
{
    int t,n,i,x;
    while(~scanf("%d",&n)&&n)
    {
        mem(a,0);
        int maxn=0;
        while(n--)
        {
            scanf("%d%d",&x,&t);
            maxn=max(maxn,t);
            a[x][t]++;
        }
        ans=0;
        te=maxn;
        dfs(5,0,0);
        printf("%d\n",ans);
    }
    return 0;
}

超时是因为大部分点都会被搜索多次，然后取其最大值，导致效率较低。看了题解才知道原来是数塔DP。。

基本思路与上面的DFS差不多，建一个二维数组，但不是从一个点往上拓展三个点，而是从一个点找到下面能够通往它的三个点，取其中最大值，加上这个点本身的值就得到这个点的dp值，只需循环一次即可找出每个最高点的最大值。

dp[i][j]表示在i秒时j位置最多可以接到多少球

dp[i][j]的最大值取决于下面三个点 dp[i-1][j-1] dp[i-1][j] dp[i-1][j+1]中的最大值，

DP代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
#define maxn 1000005

int a[maxn][12],dp[maxn][12];    //dp[i][j]表示在i秒时j位置最多可以接到多少球 

int main()
{
    int n,i,j,x,y,t;
    while(cin>>n&&n)
    {
        mem(a,0);
        int m=0;
        while(n--)
        {
            scanf("%d%d",&x,&y);
            m=max(m,y);
            a[y][x]++;
        }
        for(i=0;i<11;i++)
        	dp[0][i]=-1;			
        dp[0][5]=a[0][5];
        for(i=1;i<=m;i++)
        {
        	for(j=0;j<=10;j++)
        	{
        		int t=dp[i-1][j];
        		if(j-1>=0)
					t=max(t,dp[i-1][j-1]);
				if(j+1<=10)
					t=max(t,dp[i-1][j+1]);
				if(t!=-1)
					dp[i][j]=t+a[i][j];
				else
					dp[i][j]=-1;
			}
		}
		int t=-1;
		for(i=0;i<=10;i++)
			t=max(t,dp[m][i]);
		cout<<t<<endl;
    }
    return 0;
}