PID204 / 特种部队

/*
双向DP 两条路
 f[i][j] 表示第一条路末位置为i 第二条路末位置为j 的最优解 
转移：对于下一个点 k=max(i,j)+1 可以更新 路1的末位置 也可以更新路2的末位置
f[i][k]=min(f[i][k],f[i][j]+dis[j][k])路2 
f[k][j]=min(f[k][j],f[i][j]+dis[i][k])路1
最后 点n 可能属于路1 也可能属于路2 全枚举一遍 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1010],f[1010][1010],n,dis[1010][1010],ans=0x7fffffff;
int main()
{
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++)
      cin>>a[i];
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        dis[i][j]=abs(a[i]-a[j]);
    memset(f,127/3,sizeof(f));
    f[0][0]=0;
    for(i=0;i<=n;i++)
      for(j=0;j<=n;j++)
        {
          int k=max(i,j)+1;
          f[i][k]=min(f[i][k],f[i][j]+dis[j][k]);
          f[k][j]=min(f[k][j],f[i][j]+dis[i][k]);
        }
    for(i=1;i<=n;i++)
      {
          ans=min(ans,f[i][n]+dis[i][n]);
          ans=min(ans,f[n][i]+dis[n][i]);
      }
    cout<<ans;
    return 0;
}