题解 P5052 【[COCI2017-2018#7] Go】

· · 题解

  显而易见的一点是，当我走过了某间房子，如果这间房子里有小精灵，那么一定会把它们抓了换糖吃。由于每次只能前往相邻门牌号的房子，所以在整个比赛过程中，我访问过的房子会构成一个连续的闭区间，这个区间里的所有小精灵全部没了，而区间外的小精灵全部没有被抓。

  同时，我们也可以考虑这样一个想法：比赛者永远从一间有小精灵的房子径直走向另外一间有小精灵的房子。直观感受一下，如果中途有停留或者掉头的情况，那么时间会白白浪费而没有任何额外收益，最后收获的糖果数绝对是不增的。

  所以说，我们关注的仅仅是有小精灵的房子（还包括起点）和他们之间的距离。介于题中将小精灵按位置升序给出，我们只需挨个读入并且把起点插进去就行了。

  考虑这样一个dp，当我访问过最左端的房子为l，最右端的房子为r，目前正在左/右端（dir=0/1），而时间已经过了T秒时，最大糖果收入为dp[l][r][dir][T]。

 我们可以写出状态转移方程：

dp[l-1][r][0][T+dis(pos,l-1)]=max(dp[l-1][r][0][T+dis(pos,l-1)], dp[l][r][dir][T]+candy[l-1]*p) (l-1>0) 

dp[l][r+1][0][T+dis(pos,r+1)]=max(dp[l][r+1][0][T+ dis(pos,r+1)], dp[l][r][dir][T]+candy[r+1]*p) (r+1<=m)

  其中pos=dir ? l:r，dis函数代表两间屋子之间的距离，p则是代表该间屋子里的小精灵是否未超时的布尔变量。

  由于(1<=M<=100)，（1<=Ti<=2000），（0<=dir<=1）我们需要开一个四千万大的数组……看上去的确很大，大到一开始我压根没敢用这个做法，不过算一下也就20MB大小的内存。回头看下内存限制，嗯，512M，可以。

  先上代码吧。

#include <bits/stdc++.h>
#define LL long long
#define _ 0
#define MAXN 102
#define MAXT 2010 
#define INF 9999999
using namespace std;

int n,k,m;

struct pokeman
{
    int house,candy,tim;
}poke[MAXN]; //存储小精灵（还有起点）的信息 

int dp[MAXN][MAXN][MAXT][2];
int maxcandy=0;

inline int dis(int x,int y) //求距离函数 
{
    return abs(poke[x].house-poke[y].house);
}

void dfs(int l,int r,int tim,int dir,int candy)
{
    int pos=(dir==0 ? l:r);

    if (tim<poke[pos].tim)
        candy+=poke[pos].candy;

    if (candy<=dp[l][r][tim][dir])
        return;
    else
        dp[l][r][tim][dir]=candy;

    if (maxcandy<candy)
        maxcandy=candy;

    if (r<m-1)//向左走 
        dfs(l,r+1,tim+dis(pos,r+1),1,candy);
    if (l>0) //向右走 
        dfs(l-1,r,tim+dis(pos,l-1),0,candy);
}

int main()
{
    for (int i=0;i<MAXN;i++)
        for (int j=0;j<MAXN;j++)
            for (int s=0;s<MAXT;s++)
            {
                dp[i][j][s][0]=-1;
                dp[i][j][s][1]=-1;
            }
    //初始化 

    cin>>n>>k>>m;
    int start;
    for (int i=0;i<m;i++)
        scanf("%d%d%d",&poke[i].house,&poke[i].candy,&poke[i].tim);

    //把起点放进去，注意考虑到起点房屋有小精灵的情况。 
    for (start=0;start<m && k>poke[start].house;start++);
    if (k<poke[start].house)
        for (int j=m-1;j>=start;j--)
            poke[j+1]=poke[j];
    if (k!=poke[start].house)
    {
        m++;
        poke[start]={k,0,INF}; //把起点视为一个能换0糖果的小精灵 
    }

    dfs(start,start,0,0,0);
    cout<<maxcandy;

    return ~~(0^_^0);
}

  四千万数组的初始化可不是一个很快的工作。从我的提交结果来看，开了O2之后这一步骤仍然需要150ms左右（memset应该会快一些，不过我没试）。而假如没开O2，测试点#10已经在TLE的边缘了。

  那么能不能省略初始化的步骤？

if (candy<=dp[l][r][tim][dir])
    return;
else
    dp[l][r][tim][dir]=candy;

  原先我把dp数组初始化到-1。如果不初始化，dp数组初值为0，由于这条语句我写的是<=号，candy初值为0，0<=0，这个算法压根跑不了。

  那么改成<号行不行？

  5个刺眼的TLE狠狠地教育了我。

  事实上解决方案也简单，令candy初值为1，最后输出的结果-1即可。

  算是小蒟蒻发现的一个小技巧吧，利用全局变量初值为0的特性节省初始化时间，不知道有用没用，姑妄言之。