D - 最少花费
Time Limit: 30000/10000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
Bob是一个魔法师。这天，他被N座山所阻挡，这些山排成一排，每座山有一个高度。Bob需要从左往右每次跳到相邻的一座山上，相邻的两座山的高度差不能超过K，当从高度差为D的一座山跳到另一座山时要花A×D的魔法值。Bob可以改变一座山的高度，但调整后的高度不能小于0或大于1000，改变S的高度需要花费S×S的魔法值。现在已知每座山的高度，求Bob跳完所有山后魔法值的最少花费。
Input
第一行一个整数T(T≤150)，表示数据组数。
每组第一行有3个整数N(1≤N≤1000), K(0≤K≤1000), A(0≤A≤1000)。
接下来N个整数，按从左往右的顺序表示山的高度,山的高度在0到1000之间。
Output
对于每组数据，输出一个整数，表示最少花费。
Sample input and output
| Sample Input | Sample Output |
|---|---|
2 |
0 |
解题报告:
我们令f( i , j ) 将第 i 座山高度改为 j 的最小花费.
F( i , j ) = min ( f( i – 1 , k ) + abs ( j – k ) + (i – h[i]) ^ 2)
不妨有 j > k
F( i , j ) = min ( f( i – 1 , k ) – k ) + j + (i – h[i]) ^ 2
即维护一个单调队列来更新 j > k的情况.
J < k 的情况同理.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
typedef long long ll;
using namespace std;
const int maxn = 1e3 + ;
int a,n,dl,q[maxn];
ll f[maxn][maxn],h[maxn]; int main(int argc,char *argv[])
{
int Case;
scanf("%d",&Case);
while(Case--)
{
scanf("%d%d%d",&n,&dl,&a); //DL = deeplimit
for(int i = ; i <= n ; ++ i)
scanf("%lld",&h[i]);
for(int i = ; i <= n ; ++ i)
for(int j = ; j <= ; ++ j)
f[i][j] = ;
for(int i = ; i <= ; ++ i)
f[][i] = (i-h[])*(i-h[]);
for(int i = ; i <= n ; ++ i)
{
int front = , rear = ;
for(int j = ; j <= ; ++ j)
{
while(rear > front && f[i-][q[rear-]] - a*q[rear-] >= f[i-][j] - a*j)
rear--;
q[rear++] = j;
while(rear - front > && j > q[front] + dl)
front++;
f[i][j] = min(f[i][j],(j-h[i])*(j-h[i]) + f[i-][q[front]] + (j - q[front]) * a);
}
front = rear = ;
for(int j = ; j >= ; -- j)
{
while(rear > front && f[i-][q[rear-]] + q[rear-]*a >= f[i-][j] + j*a)
rear--;
q[rear++] = j;
while(rear - front > && q[front] > j + dl)
front++;
f[i][j] = min(f[i][j],(j-h[i])*(j-h[i]) + f[i-][q[front]] + (q[front] - j) * a );
}
}
ll ans = ;
for(int i = ; i <= ; ++ i)
ans = min(ans,f[n][i]);
printf("%lld\n",ans);
}
return ;
}