Posted on 2011-11-25 15:27
C小加 阅读(1252)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
简单DP。状态转移方程式f[i]=min(f[i],f[j]+c[k]) i站的最小花费=min(当前i站的花费，i之前的第j站的最小花费+j到i的花费c[k])
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=10003;
const int INF=0x7fffffff-1;
int l[3],c[3],n;
int a[MAXN];
int f[MAXN];
int s,t;
void Swap(int& a,int& b)
{
int temp=a;
a=b;
b=temp;
}
void DP()
{
for(int i=s+1;i<=t;i++)
{
for(int j=s;j<i;j++)
{
for(int k=0;k<3;k++)
if(a[i]-a[j]<=l[k])
f[i]=min(f[i],f[j]+c[k]);
}
}
}
int main()
{
scanf("%d %d %d %d %d %d",&l[0],&l[1],&l[2],&c[0],&c[1],&c[2]);
scanf("%d",&n);
scanf("%d %d",&s,&t);
if(s>t) Swap(s,t);
s--;
t--;
for(int i=1;i<n;i++)
{
scanf("%d",a+i);
}
for(int i=0;i<=n;i++)
{
f[i]=INF;
}
f[s]=0;
DP();
printf("%d\n",f[t]);
return 0;
}