大家好，又见面了，我是全栈君。
【题目】B. Ant Man
【题意】给定n个人的xi,ai,bi,ci,di，起点为s，终点为e，移动：
In simpler words, jumping from i-th chair to j-th chair takes exactly:
- |xi - xj| + ci + bj seconds if j < i.
- |xi - xj| + di + aj seconds otherwise (j > i).
求中间经过所有点恰好一次的最小代价。
【算法】动态规划
【题解】很巧妙的DP状态设计。（这样类似哈密顿路径的问题不能从图论方面考虑，否则很容易变成NP问题）
将代价拆分到每个点：
向左，起c+x，落b-x
向右，起d-x，落a+x
那么对于前i个点，有效信息只有这i个点中缺少多少入边和缺少多少出边。先无视s（起点）和t（终点），那么缺入边数和缺出边数相等。
令f[i][j]表示前i个点中缺少j条入/出边的最小代价，缺少入边的本质是被往左，缺少出边的本质是往右。
对于f[i-1][j]，有以下四种转移：
被往右+往右：j>0，f[i][j]=f[i-1][j]+a[i]+d[i]（两个x[i]抵消）——减少一条出边，同时增加一条出边
往左+被往左：j>0，f[i][j]=f[i-1][j]+b[i]+c[i]——减少一条入边，同时增加一条入边
被往右+往左：j>0，f[i][j-1]=f[i-1][j]+a[i]+c[i]+2*x[i]——减少一条入边和一条出边
往右+被往左：f[i][j+1]=f[i-1][j]+b[i]+d[i]-2*x[i]——增加一条入边和一条出边
最终答案为f[n][0]。
接下来解决s和t的问题，实际上s和t才能代表一个完整的点，所以将s当成一个完整的点，不把t看作一个点。
先经过s：会多一条不该有的入边，所以只要避免第二个和第三个转移。
先经过t：会少一条该有的入边，所以只要在j=0时强制进行第二个转移。
最后在到达n之前和st均有或均无时，不能成环，强制f[i][0]=inf。
复杂度O(n^2)。
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll inf=1e16,maxn=5010; ll f[maxn][maxn]; int n,s,t,x[maxn],a[maxn],b[maxn],c[maxn],d[maxn]; void m(ll &a,ll b){ if(a>b)a=b;} ll solve(){ memset(f,0x3f,sizeof(f)); int tot=0;f[0][0]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=i;j++)if(f[i-1][j]<inf){ int S=j,T=S+tot; if(i==s){ if(T)m(f[i][j],f[i-1][j]+c[i]+x[i]); m(f[i][j+1],f[i-1][j]+d[i]-x[i]); } else if(i==t){ if(S)m(f[i][j-1],f[i-1][j]+a[i]+x[i]); m(f[i][j],f[i-1][j]+b[i]-x[i]); } else{ if(S)m(f[i][j],f[i-1][j]+a[i]+d[i]); if(T)m(f[i][j],f[i-1][j]+b[i]+c[i]); if(S&&T)m(f[i][j-1],f[i-1][j]+a[i]+c[i]+2*x[i]); m(f[i][j+1],f[i-1][j]+b[i]+d[i]-2*x[i]); } } if(i==s)tot--;if(i==t)tot++; if(i!=n&&tot==0)f[i][0]=inf; } return f[n][0]; } int main(){ scanf("%d%d%d",&n,&s,&t); for(int i=1;i<=n;i++)scanf("%d",&x[i]); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&b[i]); for(int i=1;i<=n;i++)scanf("%d",&c[i]); for(int i=1;i<=n;i++)scanf("%d",&d[i]); printf("%lld",solve()); return 0; }
View Code
PS：我在这场比赛进行Virtual participation的时候，大力贪心出B……然后排名好高啊><。
至今无人能证明但AC了的贪心（似乎有人给反例）：初始s-t，然后考虑一个一个点找最优位置插入。
转载于:https://www.cnblogs.com/onioncyc/p/8277875.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107759.html原文链接：https://javaforall.net
