Description
Input
Output
* Line 1: A single integer: the minimum total staleness Bessie can achieve while eating all the clumps.
Sample Input
1
9
11
19
INPUT DETAILS:
Four clumps: at 1, 9, 11, and 19. Bessie starts at location 10.
Sample Output
OUTPUT DETAILS:
Bessie can follow this route:
* start at position 10 at time 0
* move to position 9, arriving at time 1
* move to position 11, arriving at time 3
* move to position 19, arriving at time 11
* move to position 1, arriving at time 29
giving her a total staleness of 1+3+11+29 = 44. There are other routes
with the same total staleness, but no route with a smaller one.44
f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*(n-j+i),f[i+1][j][1]+(a[j]-a[i])*(n-j+i));
f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*(n-j+i),f[i][j-1][1]+(a[j]-a[j-1])*(n-j+i));
首先我们先看第一个式子 f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*(n-j+i),f[i+1][j][1]+(a[j]-a[i])*(n-j+i));
f[i][j][0]表示牛吃完区间i到j,并停在i草地所得的腐烂值,那说明i草地是这块区间内最后被吃的,即在这之前i+1到j块草地已经被吃过了,且牛停在i+1块草地或是j块草地上,
当它之前停在i+1块草地上时,即之前的腐烂值为f[i+1][j][0]时,我们只需在之前的腐烂值上,加上第i+1块草地到第i块草地,所会带来的总腐烂值,就是现在的答案啦。
那么什么是所会带来的总腐烂值呢?当牛从i+1到i时,所需经过的路程为a[i+1]-a[i],即之后吃的每块草地都需加上这个腐烂值,总共有n-j+i(这个值是把牛最初的位置也当成一块草地的前提下推出来的,就是n-(j-i))块草地未被吃,所以之后总共要增加的腐烂值为(a[i+1]-a[i])*(n-j+i),总腐烂值就是f[i+1][j][0]+(a[i+1]-a[i])*(n-j+i),我们再把它和牛之前停在第j块草地上所需增加的腐烂值进行比较,取较小的就是f[i][j][0]的值。
第二个式子也是差不多的,可以自己去推一下。
还有一点,让我错了5次,就是一开始f[i][i][0]和f[i][i][1]是不能全部都算作无限大的,而应该赋值为它与牛初始位置之差并乘上n,即一开始就只吃那块草地所会为其他草地带去的腐烂值。
记得排序!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int n,l,j,a[],f[][][];
int main()
{
cin>>n>>l;
for (int i=;i<=n;i++) cin>>a[i];
a[n+]=l;
n+=;
sort(a+,a++n);
for (int i=;i<=n;i++)
f[i][i][]=f[i][i][]=abs(a[i]-l)*n;//这里的初始化一定要小心!
for (int len=;len<=n;len++)
for (int i=;i<=n-len+;i++)
{
j=i+len-;
f[i][j][]=min(f[i+][j][]+(a[i+]-a[i])*(n-j+i),f[i+][j][]+(a[j]-a[i])*(n-j+i));//吃完i到j这个区间并停在i所获的最小腐烂值
f[i][j][]=min(f[i][j-][]+(a[j]-a[i])*(n-j+i),f[i][j-][]+(a[j]-a[j-])*(n-j+i));//这个是停在j的
//奇怪的方程。。。在前面写过意思了
}
cout<<min(f[][n][],f[][n][])<<endl;//输出最优解。
return ;
}