首页 > ACM题库 > HDU-杭电 > HDU 4374-One hundred layer-动态规划-[解题报告]HOJ
2015
05-24

HDU 4374-One hundred layer-动态规划-[解题报告]HOJ

One hundred layer

问题描述 :

Now there is a game called the new man down 100th floor. The rules of this game is:
  1.  At first you are at the 1st floor. And the floor moves up. Of course you can choose which part you will stay in the first time.
  2.  Every floor is divided into M parts. You can only walk in a direction (left or right). And you can jump to the next floor in any part, however if you are now in part “y”, you can only jump to part “y” in the next floor! (1<=y<=M)
  3.  There are jags on the ceils, so you can only move at most T parts each floor.
  4.  Each part has a score. And the score is the sum of the parts’ score sum you passed by.
Now we want to know after you get the 100th floor, what’s the highest score you can get.

输入:

The first line of each case has four integer N, M, X, T(1<=N<=100, 1<=M<=10000, 1<=X, T<=M). N indicates the number of layers; M indicates the number of parts. At first you are in the X-th part. You can move at most T parts in every floor in only one direction.
Followed N lines, each line has M integers indicating the score. (-500<=score<=500)

输出:

The first line of each case has four integer N, M, X, T(1<=N<=100, 1<=M<=10000, 1<=X, T<=M). N indicates the number of layers; M indicates the number of parts. At first you are in the X-th part. You can move at most T parts in every floor in only one direction.
Followed N lines, each line has M integers indicating the score. (-500<=score<=500)

样例输入:

3 3 2 1
7 8 1 
4 5 6 
1 2 3 

样例输出:

29

http://acm.hdu.edu.cn/showproblem.php?pid=4374

题意:简化一下,有一个n*m的矩阵,每格有一个分数,一个人站在(1,x)位置,在每一行中,他只能朝一个方向走(向左或向右),且最多走t步,问走到最后第n行得到的最大分数。

思路:dp[i][j]表示i行 j列位置的最大分数,若从左到右,dp[i][j] = max(dp[i-1][k]+sum[j]-sum[k-1]);若从右到左,dp[i][j] = max(dp[i-1][k] +sum[j] – sum[k+1])。sum[j]在两个方程中分别表示该行 1~j的和与 j~m的和。

上述两个方程可以分别写成:

dp[i][j] = max(dp[i-1][k] – sum[k-1]) + sum[j];

dp[i][j] = max(dp[i-1][k] – sum[k+1]) + sum[j]; ( abs(j-k) <= t)

可以看出dp[i][j] 是与 sum[j]无关,而只与 dp[i-1][k] – sum[k-1] 或 dp[i-1][k] – sum[k+1] 有关。因为在(i,j)处,它最多由(i,j-t)处跳过来,每求一个dp[i][j]只需添加一个新的dp[i-1][k] – sum[k-1] 或 dp[i-1][k] – sum[k+1] 即可,而把到(i,j)的前一个点放到单调队列中,最后在单调队列中取队首就是最大值。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <list>
using namespace std;

const int INF = 0x3f3f3f3f;
int map[110][10010];
int dp[110][10010];
int sum[10010];

struct node
{
    int x;
    int data;
};

inline int maxx(int a, int b)
{
    if(a > b)
        return a;
    return b;
}
int main()
{
    int n,m,x,t;
    struct node r;
    while(~scanf("%d %d %d %d",&n,&m,&x,&t))
    {
        list <node> q;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                scanf("%d",&map[i][j]);

        for(int i = 1; i <= n; i++)
            for(int j =1; j <= m; j++)
                dp[i][j] = -INF;  //初始化为负无穷
        dp[1][x] = map[1][x];
        for(int j = x-1; j >= 1 && j >= x-t; j--)
            dp[1][j] = dp[1][j+1]+map[1][j];
        for(int j = x+1; j <= m && j <= x+t; j++)
            dp[1][j] = dp[1][j-1]+map[1][j];


        for(int i = 2; i <= n; i++)
        {
            sum[0] = 0;
            q.clear(); //清空
            for(int j = 1; j <= m; j++)
            {
                sum[j] = sum[j-1]+map[i][j];//1—j的和
                while(!q.empty() && q.front().x < j-t)
                    q.pop_front(); //把 小于 j-t的都删除,因为他们不可能到j
                int tmp = dp[i-1][j]-sum[j-1]; //要进队列
                while(!q.empty() && q.back().data <= tmp)
                    q.pop_back();//把小于tmp删除,因为他们是无意义的
                r.x = j;
                r.data = tmp;
                q.push_back(r);
                dp[i][j] = q.front().data + sum[j]; //取队首最大的
            }
            //同上,从右向左
            q.clear();
            sum[m+1] = 0;
            for(int j = m; j >= 1; j--)
            {
                sum[j] = sum[j+1]+map[i][j];
                while(!q.empty() && q.front().x > j+t)
                    q.pop_front();
                int tmp = dp[i-1][j]-sum[j+1];
                while(!q.empty() && q.back().data <= tmp)
                    q.pop_back();
                r.x = j;
                r.data = tmp;
                q.push_back(r);
                dp[i][j] = maxx(dp[i][j], q.front().data+sum[j]);
            }
        }

        int ans = dp[n][1];
        for(int i = 2; i <= m; i++)
            ans = maxx(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u013081425/article/details/21105991