MyException - 我的异常网
当前位置:我的异常网» 编程 » hdu 3698 Let the light guide us(线段树优化&

hdu 3698 Let the light guide us(线段树优化&容易DP)

www.MyException.Cn  网友分享于:2013-10-08  浏览:2次
hdu 3698 Let the light guide us(线段树优化&简单DP)

Let the light guide us

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 62768/32768 K (Java/Others)
Total Submission(s): 677    Accepted Submission(s): 226


Problem Description
Plain of despair was once an ancient battlefield where those brave spirits had rested in peace for thousands of years. Actually no one dare step into this sacred land until the rumor that “there is a huge gold mine underneath the plain” started to spread.

Recently an accident destroyed the eternal tranquility. Some greedy fools tried using powerful bombs to find the hidden treasure. Of course they failed and such behavior enraged those spirits--the consequence is that all the human villages nearby are haunted by ghosts.

In order to stop those ghosts as soon as possible, Panda the Archmage and Facer the great architect figure out a nice plan. Since the plain can be represented as grids of N rows and M columns, the plan is that we choose ONLY ONE cell in EACH ROW to build a magic tower so that each tower can use holy light to protect the entire ROW, and finally the whole plain can be covered and all spirits can rest in peace again. It will cost different time to build up a magic tower in different cells. The target is to minimize the total time of building all N towers, one in each row.

“Ah, we might have some difficulties.” said Panda, “In order to control the towers correctly, we must guarantee that every two towers in two consecutive rows share a common magic area.”

“What?”

“Specifically, if we build a tower in cell (i,j) and another tower in cell (i+1,k), then we shall have |j-k|≤f(i,j)+f(i+1,k). Here, f(i,j) means the scale of magic flow in cell (i,j).”

“How?”

“Ur, I forgot that you cannot sense the magic power. Here is a map which shows the scale of magic flows in each cell. And remember that the constraint holds for every two consecutive rows.”

“Understood.”

“Excellent! Let’s get started!”

Would you mind helping them?
 

Input
There are multiple test cases.

Each test case starts with a line containing 2 integers N and M (2<=N<=100,1<=M<=5000), representing that the plain consists N rows and M columns.

The following N lines contain M integers each, forming a matrix T of N×M. The j-th element in row i (Tij) represents the time cost of building a magic tower in cell (i, j). (0<=Tij<=100000)

The following N lines contain M integers each, forming a matrix F of N×M. The j-th element in row i (Fij) represents the scale of magic flows in cell (i, j). (0<=Fij<=100000)

For each test case, there is always a solution satisfying the constraints.

The input ends with a test case of N=0 and M=0.
 

Output
For each test case, output a line with a single integer, which is the minimum time cost to finish all magic towers.
 

Sample Input
3 5 9 5 3 8 7 8 2 6 8 9 1 9 7 8 6 0 1 0 1 2 1 0 2 1 1 0 2 1 0 2 0 0
 

Sample Output
10
 

Source
2010 Asia Fuzhou Regional Contest
 

Recommend
chenyongfu
 

题意:

要在N*M(n<=100.m<=5000)的矩形区域的每行的一个位置建灯塔。而在第i行的j列建塔要花费时间ti[i][j].建塔还必须满足一个条件。

如果本行在j列建塔。下行在k列建塔。那么必须满足|j-k|<=f[i][j]+f[i+1][k]。

f[i][j]由题目给出。

问每行建完塔花费的最小时间。

思路:

很容易想到一个动规方程。dp[i][j]=min(dp[i][j],dp[i-1][k]+ti[i][j])。dp[i][j]代表前面i-1行建好塔。第i行在j列建塔的最小花费。

可问题又来了。这个k怎么确定。。。。。

如果暴力枚举的话时间复杂度为O(n*m*m)。目测最好n,m取最大的时候大于9秒吧。这还是单组数据。。。

所以不得不找其它办法优化下。

这个估计就要点思维了。我也是看了别人的转化才恍然大悟的。

我们去掉绝对值可以得到两个方程。

j-f[i][j]<=k+f[i+1][k]。 j>=k。

k-f[i+1][k]<=j+f[i][j]。 j<k。

可以发现k的取值范围即为区间[j-f[i][j],j+f[i][j]]和[k-f[i+1][k],k+f[i+1][k]]相交的部分。

所以思路就清晰了。要求dp[i][j]只需要知道上一行和[j-f[i][j],j+f[i][j]]相交部分的最小值就可以了。

而这个值可以用线段树维护。时间复杂度降到了。O(n*m*log(m))这下就没问题了。

详细见代码:

#include<algorithm>
#include<iostream>
#include<sstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=150;
const int maxm=5010;
int ti[maxn][maxm],f[maxn][maxm],minv[maxm<<2],lazy[maxm<<2];
int dp[maxm],n,m;
void btree(int L,int R,int k)
{
    int ls,rs,mid;

    minv[k]=lazy[k]=INF;
    if(L==R)
        return ;
    ls=k<<1;
    rs=ls|1;
    mid=(L+R)>>1;
    btree(L,mid,ls);
    btree(mid+1,R,rs);
}
void pushdown(int k,int ls,int rs)
{
    minv[ls]=min(minv[ls],lazy[k]);
    minv[rs]=min(minv[rs],lazy[k]);
    lazy[ls]=min(lazy[ls],lazy[k]);
    lazy[rs]=min(lazy[rs],lazy[k]);
    lazy[k]=INF;
}
void update(int L,int R,int l,int r,int k,int v)
{
    int ls,rs,mid;
    if(L==l&&R==r)
    {
        minv[k]=min(minv[k],v);
        lazy[k]=min(lazy[k],v);
        return;
    }
    ls=k<<1;
    rs=ls|1;
    mid=(L+R)>>1;
    if(lazy[k]!=INF)
        pushdown(k,ls,rs);
    if(l>mid)
        update(mid+1,R,l,r,rs,v);
    else if(r<=mid)
        update(L,mid,l,r,ls,v);
    else
    {
        update(L,mid,l,mid,ls,v);
        update(mid+1,R,mid+1,r,rs,v);
    }
    minv[k]=min(minv[ls],minv[rs]);
}
int qu(int L,int R,int l,int r,int k)
{
    int ls,rs,mid;
    if(L==l&&R==r)
        return minv[k];
    ls=k<<1;
    rs=ls|1;
    mid=(L+R)>>1;
    if(lazy[k]!=INF)
        pushdown(k,ls,rs);
    if(l>mid)
        return qu(mid+1,R,l,r,rs);
    else if(r<=mid)
        return qu(L,mid,l,r,ls);
    else
        return min(qu(L,mid,l,mid,ls),qu(mid+1,R,mid+1,r,rs));

}
int main()
{
    int i,j,l,r,ans;

    while(scanf("%d%d",&n,&m),n||m)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&ti[i][j]);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&f[i][j]);
        for(i=1;i<=m;i++)
            dp[i]=ti[1][i];
        for(i=2;i<=n;i++)
        {
            btree(1,m,1);
            for(j=1;j<=m;j++)
            {
                l=max(j-f[i-1][j],1);
                r=min(j+f[i-1][j],m);
                update(1,m,l,r,1,dp[j]);
            }
            for(j=1;j<=m;j++)
            {
                l=max(j-f[i][j],1);
                r=min(j+f[i][j],m);
                dp[j]=qu(1,m,l,r,1)+ti[i][j];
            }
        }
        ans=INF;
        for(i=1;i<=m;i++)
            ans=min(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}


文章评论

老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
每天工作4小时的程序员
每天工作4小时的程序员
我是如何打败拖延症的
我是如何打败拖延症的
中美印日四国程序员比较
中美印日四国程序员比较
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员和编码员之间的区别
程序员和编码员之间的区别
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
为什么程序员都是夜猫子
为什么程序员都是夜猫子
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
Java程序员必看电影
Java程序员必看电影
 程序员的样子
程序员的样子
旅行,写作,编程
旅行,写作,编程
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
漫画:程序员的工作
漫画:程序员的工作
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
编程语言是女人
编程语言是女人
代码女神横空出世
代码女神横空出世
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
一个程序员的时间管理
一个程序员的时间管理
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
总结2014中国互联网十大段子
总结2014中国互联网十大段子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
我的丈夫是个程序员
我的丈夫是个程序员
10个调试和排错的小建议
10个调试和排错的小建议
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
鲜为人知的编程真相
鲜为人知的编程真相
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员必看的十大电影
程序员必看的十大电影
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员都该阅读的书
程序员都该阅读的书
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有