甲虫喝水题解

题目来源：NOI导刊，NOIP模拟试题八
题目描述：有一只甲虫位于x轴的原点，在任何时刻，它可以选择左右两个方向移动，并且移动一个单位长度需要耗时1s。x轴上的N个点上有露珠。起始时刻，每个露珠的含水量都是正整数M，每经过1s，每个露珠的含水量减少1单位。当甲虫遇到露珠时，它可以在瞬间喝光露珠的水。
输入N,M和每个露珠的位置（露珠位置为整数），输出甲虫能喝到的最多的水量。

比如：N=3 M=15 露珠位置分别为6、-3、1时，甲虫可以依次喝1、-3、6处的露水，获得最大水量25

可以明确一下几点：

1. 甲虫只会在有露珠的位置掉转方向。
2. 一旦遇到露珠，甲虫一定会喝掉。
3. 每个时刻所有未喝掉的露珠水量都会均匀减少。

故甲虫喝掉的水一定是一个连续的区间。

因此，这个题目就是一道区间动规题。
首先，先对露珠的位置排序。
用fi[i][j][k]表示一共要吃掉k颗露水，目前吃光了i到j之间的露水并停留在i端的情况。fj[i][j][k]表示停留在j端的情况。增加k这一维，预先扣除剩余(k-i+j)颗露水的减少量，就可以解决露珠水量减少的问题。

具体的转移方程可以参考下面的代码。数组中k这一维可以压缩掉。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 303

long x[MAXN];
long N,M;
long ans;
long fi[MAXN][MAXN];
long fj[MAXN][MAXN];

int cmp(const void *a,const void *b)
{
   if(*(long *)a > *(long *)b)    return 1;
   return -1;
}

void init()
{
   scanf("%ld%ld",&N,&M);
   long i;
   for(i = 0;i < N;i ++)
       scanf("%ld",&x[i]);
   qsort(x,N,sizeof(long),cmp);
}

inline long getmax(long a,long b)
{
   if(a > b)    return a;
   return b;
}

void solve()
{
   ans = 0;
   int i,j,k,l;
   for(k = 1;k <= N;k ++)
   {
       for(i = 0;i < N;i ++)
       {
           fi[i][i] = fj[i][i] = M - labs(x[i]) * k;
           ans = getmax(ans,fi[i][i]);
       }
       for(l = 2;l <= k;l ++)
           for(i = 0;i <= N - l;i ++)
           {
               j = i + l - 1;
               fi[i][j] = M + getmax(fi[i + 1][j] - (x[i + 1] - x[i]) * (k - j + i),fj[i + 1][j] - (x[j] - x[i]) * (k - j + i));
               fj[i][j] = M + getmax(fi[i][j - 1] - (x[j] - x[i]) * (k - j + i),fj[i][j - 1] - (x[j] - x[j - 1]) * (k - j + i));
               ans = getmax(fi[i][j],ans);
               ans = getmax(fj[i][j],ans);
           }
   }
   printf("%ld\n",ans);
}

int main()
{
   freopen("beetle.in","r",stdin);
   freopen("beetle.out","w",stdout);
   init();
   solve();
   return 0;
}