Dragon Ball

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

1
3 2 5
2 3
4 1
1 3
1 1
1 3
4 2

8

题意：有一条线，有m周期，在每个周期在线上的n个点会出现一个龙珠，同时给你初始的点，在每个周期必须去取一个且只能取一个龙珠，取龙珠的消耗为当前点到龙珠所在的距离和挖取龙珠的消耗总和，问在m个周期取m个龙珠的最小消耗为多少。

题解：状态转移为dp[i][j]=min{dp[i-1][k]+|pos[i][j]-pos[i-1][k]|}+cost[i][j](1<=k<=n)，这个需要o(n^3)的时间复杂度，如果人品够好还是能过的，但是这个明显不是正解。我们可以分pos[i][j]<pos[i-1][k]和pos[i][j]>pos[i-1][k]两种情况讨论，此时绝对值就可以去掉了，发现这个最值和j没有关系，我们做些预处理就可以提高效率了。

二分搜索版：

ps:g++能过，c++WA这个好神奇啊，猜测是二分写的有问题，求路过的大神指导。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define inf 0x7fffffff
#define ab(x) ((x)>0?(x):-(x))
struct point
{
    int mat;
    int dig;
}node[55][1005];
int dp[55][1005];
int num[1010];
int l[1005],r[1005];
int n,m;
bool tmp(const point &a,const point &b)
{
    return a.mat<b.mat;
}
//二分查找求上界
int find_upper(int x,int i)
{
    if(x>node[i-1][m].mat) return -1;
    int lx=1,rx=m,mid;
    for(;rx>lx;)
    {
        mid=(lx+rx)/2;
        if(node[i-1][mid].mat>x)
            rx=mid;
        else if(node[i-1][mid].mat<x)
            lx=mid+1;
        else return mid;
    }
    return rx;
}
//二分查找求下界
int find_lower(int x,int i)
{
    if(x<node[i-1][1].mat) return -1;
    int lx=1,rx=m,mid;
    for(;rx>lx;)
    {
        mid=(lx+rx+1)/2;
        if(node[i-1][mid].mat<x)
            lx=mid;
        else if(node[i-1][mid].mat>x)
            rx=mid-1;
        else return mid;

    }
    return lx;
}
int main()
{
    int T;
    int x;
    scanf("%d",&T);
    for(; T--;)
    {
        scanf("%d%d%d",&n,&m,&x);
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d",&node[i][j].mat);
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d",&node[i][j].dig);
        for(int i=1;i<=n;++i)
            sort(node[i]+1,node[i]+m+1,tmp);
        //初始化
        for(int i=2; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                dp[i][j]=inf;
        for(int i=1; i<=m; ++i)
            dp[1][i]=ab(x-node[1][i].mat)+node[1][i].dig;
        for(int i=2; i<=n; ++i)
        {
            int minn=inf;
            for(int j=1;j<=m;++j)
            {
                if(minn>dp[i-1][j]-node[i-1][j].mat)
                   minn=dp[i-1][j]-node[i-1][j].mat;
                l[j]=minn;
            }
            minn=inf;
            for(int j=m;j>=1;--j)
            {
                if(minn>dp[i-1][j]+node[i-1][j].mat)
                   minn=dp[i-1][j]+node[i-1][j].mat;
                r[j]=minn;
            }
            for(int j=1; j<=m; ++j)
            {
                int rx=find_upper(node[i][j].mat,i);
                int lx=find_lower(node[i][j].mat,i);
                if(lx!=-1)
                    dp[i][j]=min(dp[i][j],l[lx]+node[i][j].mat);
                if(rx!=-1)
                    dp[i][j]=min(dp[i][j],r[rx]-node[i][j].mat);
                dp[i][j]+=node[i][j].dig;
            }
        }
        int ans=inf;
        for(int i=1; i<=m; ++i)
            ans=min(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

单调队列版本：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define inf 0xfffffff
#define ab(x) ((x)>0?(x):-(x))
struct point
{
    int mat;
    int dig;
} node[55][1005];
int dp[55][1005];
bool cmp(const point &a,const point &b)
{
    return a.mat<b.mat;
}
int main()
{
    int T,x,n,m;
    scanf("%d",&T);
    for(; T--;)
    {
        scanf("%d%d%d",&n,&m,&x);
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d",&node[i][j].mat);
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d",&node[i][j].dig);
        for(int i=1; i<=n; ++i)
            sort(node[i]+1,node[i]+m+1,cmp);
        for(int i=2; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                dp[i][j]=inf;
        for(int i=1; i<=m; ++i)
            dp[1][i]=ab(x-node[1][i].mat)+node[1][i].dig;
        for(int i=2; i<=n; ++i)
        {
            int idx=1,minn=inf;//下标和最值
            for(int j=1; j<=m; ++j)
            {
                for(;idx<=m&&node[i][j].mat>=node[i-1][idx].mat;++idx)
                {
                    minn=min(minn,dp[i-1][idx]-node[i-1][idx].mat);
                }
                dp[i][j]=min(dp[i][j],minn+node[i][j].mat);
            }
            idx=m,minn=inf;//下标和最值
            for(int j=m; j>=1; --j)
            {
                for(;idx>=1&&node[i][j].mat<=node[i-1][idx].mat;--idx)
                {
                    minn=min(minn,dp[i-1][idx]+node[i-1][idx].mat);
                }
                dp[i][j]=min(dp[i][j],minn-node[i][j].mat);
            }
            for(int j=1; j<=m; ++j)
                dp[i][j]+=node[i][j].dig;
        }
        int ans=inf;
        for(int i=1; i<=m; ++i)
            ans=min(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

来源：http://blog.csdn.net/ACM_Ted