1742: [Usaco2005 nov]Grazing on the Run
http://www.lydsy.com/JudgeOnline/problem.php?id=1742
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 371695 | Liu_Ts | 1742 | Accepted | 8796 kb | 96 ms | C++ | 757 B | 2013-03-19 16:58:10 |
大意
数轴上有N个点，起点为额外的P点，在某个点被到达之前，这个点每单位时间会消费1点费用，到达后不再产生费用。求遍历所有点花费的最小费用。
题解
区间DP，
L(a,b) 表示已经走完a到b，且当前在a点的最小花费；
R(a,b) 表示已经走完a到b，且当前在a点的最小花费；
则：
L(a,b) = min( L(a+1,b) + |x(a)-x(a+1)|, R(a+1,b) + |x(a)-x(b)| )
R(a,b) = min( R(a,b-1) + |x(b)-x(b-1)|, L(a,b-1) + |x(b)-x(a)| )
Ans = min(L(1,n), R(1,n))
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1011;
int n,a[N],L[N][N],R[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
a[++n]=0;
sort(a+1,a+1+n);
int t=lower_bound(a+1,a+1+n,0)-a;
memset(L,60,sizeof(L));
memset(R,60,sizeof(R));
L[t][t]=R[t][t]=0;
for(int l=2;l<=n;l++)
for(int i=1;i<=n;i++)
{
int j=i+l-1;
if(j>n) continue;
L[i][j]=min(L[i+1][j]+(n-l+1)*(a[i+1]-a[i]),
R[i+1][j]+(n-l+1)*(a[j]-a[i]));
R[i][j]=min(L[i][j-1]+(n-l+1)*(a[j]-a[i]),
R[i][j-1]+(n-l+1)*(a[j]-a[j-1]));
}
printf("%d\n",min(L[1][n],R[1][n]));
}
评论 (0)
