题意与分析

中文题就不讲题意了。我是真的菜，菜出声。

不妨思考一下，限制了我们决策的有哪些因素？一，所在的位置；二，所在的时间。还有吗？没有了，所以设dp[i][j]" role="presentation">dp[i][j]dp[i][j]为第i秒在j处的最大馅饼数，有：

dp[i][j]=dp[i][j]=max(dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1])+f[i][j]" role="presentation">dp[i][j]=dp[i][j]=max(dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1])+f[i][j]dp[i][j]=dp[i][j]=max(dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1])+f[i][j]

是不是很显然？然后就去快乐做题了对不对？

你就会想：从小到大推还是从大到小推？

从大到小推。因为如果从小到大推，无法反映出一次只能移动一格的特性；相反，从大到小推只需要最后直接求dp[0][5]即可。

这题说明了对于状态转移方程的思考一定要彻底，不能想当然。

代码

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

template<typename T>

T read()

{

    T tmp; cin>>tmp;

    return tmp;

}

int f[100005][12],dp[100005][12],n;

int main()

{

QUICKIO

    while(cin>>n)

    {

        if(!n) break;

        ZERO(f); ZERO(dp);

        // dp[i][j] 第i秒在第j米处能获得的最多馅饼数目

        // dp[i][j] = max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+f[i][j]

        int maxsec=0;

        rep(i,1,n)

        {

            int x,y; cin>>x>>y;

            f[y][x]++;

            maxsec=max(y,maxsec);

        }

//        cout<<maxsec<<endl;

        per(i,maxsec-1,0)

        {

            //cout<<i<<":\n";

            rep(j,0,10)

            {

                //if(i==1 && j<4 && j>6) continue;

                int maxans=-1;

                if(j-1>=0) maxans=max(f[i+1][j-1],maxans);

                maxans=max(f[i+1][j],maxans);

                if(j+1<=10) maxans=max(f[i+1][j+1],maxans);

                f[i][j]=maxans+f[i][j];

            }

            /*

            rep(j,0,10)

            {

                cout<<f[i][j]<<" ";

            }

            cout<<endl;

            */

        }

        cout<<f[0][5]<<endl;

    }

    return 0;

}

巴特西

「暑期训练」「基础DP」免费馅饼（HDU-1176）

题意与分析

代码

最新文章

热门文章