题解 P1070 【道路游戏】

ButterflyDew · 2018-06-22 21:18:23 · 题解

写这个题真是累啊，好毒。应该练练处理比较麻烦的DP。

在读完题目以后，其实初始版的方程并不难想

$k$那一维可以通过直接枚举消去 $dp[i][j][1/0]$表示时间$i$工厂$j$是否能够继续再走转移为 $dp[i][j][1]=max(dp[i][j][1],dp[i-k][j-k][0]+cal(i,j,k))$//没有列出关于环的情况的，以下会详细说 $dp[i][j][0]=max(dp[i][j][0],dp[i][k][1]-cost[j])

确实很不完美，我当时也只是想到了这么多，感觉过个90还是比较轻松的，1000的点拿单调队列优化一下就行了。

然后我就开始写cal函数，处理那个对角线式的前缀和，然后成功把自己搅糊了。

这个题把点权释放到了边权上，人话就是存储的路径位置其实是某个点伸出去的那一条

比如用这个图来描述读入的某时间某费用数组

![](http://m.qpic.cn/psb?/V14VFGnz4fbJRr/6YV.sneltfuZ53B.vTuVQpXvIvFx1o633f*CkCB8vmA!/b/dEABAAAAAAAA&bo=4QJrAeECawEDCSw!&rf=viewer_4) 好吧，弄清楚了这个，写一下$cal(i,j,k)$函数了，如下图，它要返回这样一个链的值 ![](http://m.qpic.cn/psb?/V14VFGnz4fbJRr/u*PMefg5t4pVbB94AgrkwBVsNVyWjjtUhfSzz1Fif3o!/b/dC8BAAAAAAAA&bo=vAKKAbwCigEDCSw!&rf=viewer_4) 事实上看起来也不是那么麻烦 ``` int cal(int i,int j,int k) { return f[i-1][j-1]-f[i-k-1][j-k-1]; } ``` 但是，当转移设计到拐弯时 ![](http://m.qpic.cn/psb?/V14VFGnz4fbJRr/u*PMefg5t4pVbB94AgrkwBVsNVyWjjtUhfSzz1Fif3o!/b/dC8BAAAAAAAA&bo=vAKKAbwCigEDCSw!&rf=viewer_4) 确实有点麻烦。。。我最开始漏掉了那条虚线。。这是带拐弯的转移：$dp[i][j][1]=max(dp[i][j][1],dp[i-k][n+j-k][0]+cal(i-j+1,n+1,k-j+1)+cal(i,j,j-1))

好吧，到这里我已经感觉我写不出单调队列了。

交了一下果然拿到了90分，其实在如果在考场上做到这里已经可以了（鬼知道为什么部分分有这么多）

部分分代码：

#include <cstdio>
#include <cstring>
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
const int N=1010;
const int inf=0x3f3f3f3f;
int dp[N][N][2],n,m,p,harv[N][N],f[N][N],cost[N],ans=-inf;//n数量，m时间
int cal(int i,int j,int k)
{
    return f[i-1][j-1]-f[i-k-1][j-k-1];
}
int main()
{
    memset(dp,-0x3f,sizeof(dp));
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&harv[i][j]);
            f[j][i]=f[j-1][i-1]+harv[i][j];
        }
    for(int i=1;i<=n;i++)
        scanf("%d",cost+i);
    for(int i=1;i<=n;i++)
        dp[1][i][0]=-cost[i];
    m++;
    for(int i=2;i<=m;i++)//时间
    {
        for(int j=1;j<=n;j++)//路程
        {
            for(int k=1;k<=min(i,p);k++)//从第几个之前转移
            {
                if(j>k)
                    dp[i][j][1]=max(dp[i][j][1],dp[i-k][j-k][0]+cal(i,j,k));
                else if(i>j)
                    dp[i][j][1]=max(dp[i][j][1],dp[i-k][n+j-k][0]+cal(i-j+1,n+1,k-j+1)+cal(i,j,j-1));
            }

        }
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
            {
                if(k==j) continue;
                dp[i][j][0]=max(dp[i][j][0],dp[i][k][1]-cost[j]);
            }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[m][i][1]);
    printf("%d\n",ans);
    return 0;
}

看看各位佬爷的题解。

才发现自己的方程太不优秀了，优秀的方程O(N^3)甚至可以卡过。

转移：$dp[i]=max(dp[i-k]+cal(i,j,k)-cost[j-k])$//无环看着减去的$cost[i]$，我明白了应该给$dp[i]$加一个定语 $dp[i]$表示时间$i$处在某位置上还未在此位置上消费机器人的最大答案，每一步的机器人花费是在被转移的时候才扣得啊。而我最初的方程，是代表当前时间$i$和地点$j$已经买了机器人的最大答案。为了区分是否处理花费机器人的状态，我甚至得用第三维的0/1维护。读了读题目中**“必须立刻在任意一个机器人工厂中购买一个新的机器人”**，我明白了为什么可以不要地点这一维，其实每一个时间都可以当做是步数已经到了的时间，而此时地点的选择是具有任意性的，即此时地点也是不重要的。我把方程改了改，果然$O(N^3)$卡过了 ------------ ### 单调队列优化但是，如果数据再卡一点，单队优化就是必须的了。在这里，因为实在是觉得这种点权下放的方式不优雅，我将工厂的实际编号和时间给减去了1，而读入时不变 ![](http://m.qpic.cn/psb?/V14VFGnz4fbJRr/zLicmWslxFNVhjDepk9XfsmJIJUG5FN7DgQDNQQQVMI!/b/dDABAAAAAAAA&bo=yAJ*AcgCfwEDCSw!&rf=viewer_4) 这样，查询$f[i][j]$所代表的就不是再多延伸出去一条链了，很舒服了。再列出转移方程：//无环 $dp[i]=max(dp[i-k]+f[i][j]-f[i-k][j-k]-cost[j-k])

=max(dp[i-k]-f[i-k][j-k]-cost[j-k])+f[i][j]

转移时维护q[i][j]=dp[i]-f[i][j]-cost[j]即可

因为每一个f[i][j]都可以唯一的确定一个dp[i]和cost[j]，所以我们考虑f[i][j]在转移时的分布。

对同一个答案的贡献，这个分布大概是这样。

为了准确的定位某个答案从哪个单调队列转移，考虑给每一个单调队列编号，将单队与location轴相交的那个点作为它的编号。

在还没拐弯时，所属单队即为j-i，拐弯了以后我们发现它减去了l个n，l为拐弯次数，很简单，取膜以后加一个再取膜即可

int get(int i,int j)//获取单队编号
{
    return ((j-i)%n+n)%n;
}

还有两点要注意的地方

一是虚线所连的边仍然需要特判一下二是为了确保拐弯后不出现问题，要把dp[i]=max(dp[i-k]-f[i-k][j-k]-cost[j-k])+f[i][j]中的f[i][j]加上它失去的链的长度，维护一个add[i]数组。

参考代码：

#include <cstdio>
#include <cstring>
const int N=1010;
int max(int x,int y){return x>y?x:y;}
int n,m,p;
int f[N][N],cost[N],q[N][N],loc[N][N],l[N],r[N],add[N],dp[N];
int get(int i,int j)//获取单队编号
{
    return ((j-i)%n+n)%n;
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&f[j][i]);
            f[j][i]+=f[j-1][i-1];
        }
    for(int i=0;i<n;i++)
    {
        scanf("%d",cost+i);
        q[i][++r[i]]=-cost[i],l[i]++;
    }
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<n;j++)
        {
            int id=get(i,j);
            while(l[id]<=r[id]&&loc[id][l[id]]+p<i) l[id]++;
            if(!j) add[id]+=f[i][n];
            if(l[id]<=r[id])
                dp[i]=max(dp[i],q[id][l[id]]+add[id]+f[i][j]);
        }
        for(int j=0;j<n;j++)
        {
            int id=get(i,j);
            int tmp=dp[i]-add[id]-f[i][j]-cost[j];
            while(l[id]<=r[id]&&q[id][r[id]]<=tmp)
                r[id]--;
            loc[id][++r[id]]=i;
            q[id][r[id]]=tmp;
        }
    }
    printf("%d\n",dp[m]);
    return 0;
}