这道题是宁波集训的那道题，讲课时轻描淡写吧（应该是我听课不认真罢了），所以这样就要靠自己的理解了，
dp[i][j][0]表示从左端点开始完成整个区间的最小花费dp[i][j][1]表示从右端点开始完成整个区间的最小花费，就是这样的。
然后记录前驱，因为每次只会从端点开始，不然返回端点的时间是不必要的，这样就可以了，然后最后输出即可。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std; const int NN=,INF=1e9+; int n;
int t[NN],d[NN];
int f[NN][NN][],fa[NN][NN][]; int main()
{
while (~scanf("%d",&n))
{
memset(f,,sizeof());
memset(fa,,sizeof(fa));
for (int i=;i<=n;i++)
scanf("%d",&t[i]);
for (int i=;i<=n;i++)
scanf("%d",&d[i]);
memset(f,,sizeof(f));
for (int k=;k<=n;k++)
{
for (int i=;i+k-<=n;i++)
{
int j=i+k-;
if (f[i+][j][]+d[i+]-d[i]<f[i+][j][]+d[j]-d[i])
{
f[i][j][]=f[i+][j][]+d[i+]-d[i];
fa[i][j][]=;
}
else
{
f[i][j][]=f[i+][j][]+d[j]-d[i];
fa[i][j][]=;
}
if (f[i][j][]>=t[i]||f[i][j][]>INF) f[i][j][]=INF;//没什么大不了的，防止溢出。
if (f[i][j-][]+d[j]-d[j-]<f[i][j-][]+d[j]-d[i])
{
f[i][j][]=f[i][j-][]+d[j]-d[j-];
fa[i][j][]=;
}
else
{
f[i][j][]=f[i][j-][]+d[j]-d[i];
fa[i][j][]=;
}
if (f[i][j][]>=t[j]||f[i][j][]>INF) f[i][j][]=INF;//没什么大不了的，防止溢出。
}
}
int l,r,w;
if (f[][n][]<INF)
{
printf("");
l=,r=n,w=fa[][n][];
}
else if (f[][n][]<INF)
{
printf("%d",n);
l=,r=n-,w=fa[][n][];
}
else
{
printf("Mission Impossible\n");
continue;
}
while (l<=r)
{
if (w==)
{
printf(" %d",l);
w=fa[l][r][],l++;
}
else
{
printf(" %d",r);
w=fa[l][r][],r--;
}
}
printf("\n");
}
}