题目链接:http://codeforces.com/problemset/problem/704/B
--------------------------------------------------------------------------------
比赛时最远也就猜到了拆公式,算贡献这一步 然后就$GG$了
结束后问了$Randolph87$ 他给了一个"括号匹配"的思路
感觉这个思路比官方题解更可做 然后我就按照这个思路开始思考
对于非起点非终点外的所有点 有这四种情况
左入左出 左入右出 右入左出 右入右出
每当加入一个新的点
如果它是右入右出则当前区间的入度 $+1$ 出度 $+1$
如果是左入左出则当前区间的入度 $-1$ 出度 $-1$
另外两种情况则是入度出度都不改变
(此处度数是对于整个区间讲的 或者说这个区间对应的有向图还需要增加$x$个入度和$y$个出度才能构成一个环)
假设题目不限定起点终点 只要求一个回路 那么对于所有的点都这样做
并且保证中间状态中入度出度都为正数 最终状态入度出度都为$0$即可
然而题目是有起点和终点限制的一条路径
因此我们可以强行连一条从终点出从起点入的代价为$0$的边
.
.
.
按照这个思路做下去 一部分人会$WA5$
原因是在实现的时候 有可能只是限定了终点有一条方向向着起点的边
于是中间还可能混入其他的点 并没有保证终点和起点的直接连接
为了满足这个要求 我们可以在扫描到起点和终点之间的点的时候
强行使得 入度$-1(s < e$时$)$ / 出度 $-1(s > e$时$)$
这样就可以把这一部分完美地解决了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = ;
long long f[N][N];
bool valid[N][N];
int x[N], a[N], b[N], c[N], d[N];
int n, s, e;
void update(long long &x, long long y, bool &z)
{
if(!z)
{
z = ;
x = y;
return;
}
x = min(x, y);
}
int main()
{
scanf("%d%d%d", &n, &s, &e);
for(int i = ; i <= n; ++i)
scanf("%d", &x[i]);
for(int i = ; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = ; i <= n; ++i)
scanf("%d", &b[i]);
for(int i = ; i <= n; ++i)
scanf("%d", &c[i]);
for(int i = ; i <= n; ++i)
scanf("%d", &d[i]);
valid[][] = ;
int delta = ;
for(int i = ; i <= n; ++i)
{
if(i == min(s, e))
delta = s < e ? : -;
else if(i == max(s, e))
delta = ;
if(i != s && i != e)
for(int j = ; j <= i && j <= n - i; ++j)
{
if(j && valid[i - ][j - ])
update(f[i][j], f[i - ][j - ] + b[i] + d[i] - x[i] * , valid[i][j]);
if((j || i == n) && valid[i - ][j + ])
update(f[i][j], f[i - ][j + ] + a[i] + c[i] + x[i] * , valid[i][j]);
if(j && valid[i - ][j])
{
if(j > || !delta)
update(f[i][j], f[i - ][j] + min(a[i] + d[i], b[i] + c[i]), valid[i][j]);
else if(delta == )
update(f[i][j], f[i - ][j] + a[i] + d[i], valid[i][j]);
else
update(f[i][j], f[i - ][j] + b[i] + c[i], valid[i][j]);
}
}
else if(i == s)
for(int j = ; j <= i && j <= n - i; ++j)
{
if(s < e && j && valid[i - ][j - ])
update(f[i][j], f[i - ][j - ] + d[i] - x[i], valid[i][j]);
if(s < e && j && valid[i - ][j])
update(f[i][j], f[i - ][j] + c[i] + x[i], valid[i][j]);
if(s > e && (j || i == n) && valid[i - ][j + ])
update(f[i][j], f[i - ][j + ] + c[i] + x[i], valid[i][j]);
if(s > e && j && valid[i - ][j])
update(f[i][j], f[i - ][j] + d[i] - x[i], valid[i][j]);
}
else
for(int j = ; j <= i && j <= n - i; ++j)
{
if(s < e && (j || i == n) && valid[i - ][j + ])
update(f[i][j], f[i - ][j + ] + a[i] + x[i], valid[i][j]);
if(s < e && j && valid[i - ][j])
update(f[i][j], f[i - ][j] + b[i] - x[i], valid[i][j]);
if(s > e && j && valid[i - ][j - ])
update(f[i][j], f[i - ][j - ] + b[i] - x[i], valid[i][j]);
if(s > e && j && valid[i - ][j])
update(f[i][j], f[i - ][j] + a[i] + x[i], valid[i][j]);
}
}
printf("%lld\n", f[n][]);
return ;
}