KM 做法这么简单好想为什么都在 dp?我第一次过也是用的 dp。
建模非常好想,每天只能收一次钱,最简单的思路是我们枚举第几天开车跑路,但是再一想我们不关心是第几天,只关心每次贷款离开车跑路还差几天,于是我们从 i 向 j 连边,边权是 ai+bi×min(ki,j),意义为第 i 种贷款离买车还差 j 天对答案的贡献,当然我们实现时需要对 0 取最大值,因为取 0 的意义为不参与答案贡献,然而我们并不要求在最后一天开车,所以对 0 取最大值是必要的。
并且,容易证明我们不可能在某一天没有进行任何操作。
所以建完模直接跑 KM 算法即可,时间复杂度 O(n3)。
代码:
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define eb emplace_back
#define inf 1000000000
#define linf 10000000000000000
#define pii pair <int, int>
using namespace std;
constexpr int N = 505, P = 1e9 + 7;
inline int rd ()
{
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
return x * f;
}
int n, sum, ans;
int e[N][N];
int lx[N], ly[N], px[N], py[N], pre[N], slack[N];
bool vx[N], vy[N], flag;
int a[N], b[N], k[N];
queue <int> q;
void aug (int v)
{
while (v)
{
int t = px[pre[v]];
px[pre[v]] = v;
py[v] = pre[v];
v = t;
}
}
void bfs (int s)
{
memset (vx, 0, sizeof vx);
memset (vy, 0, sizeof vy);
memset (slack, 127, sizeof slack);
while (! q.empty ()) q.pop ();
q.push (s);
while (true)
{
while (! q.empty ())
{
int u = q.front ();
q.pop ();
vx[u] = 1;
rep (i, 1, n)
{
if (vy[i]) continue;
if (lx[u] + ly[i] - e[u][i] < slack[i])
{
slack[i] = lx[u] + ly[i] - e[u][i];
pre[i] = u;
if(! slack[i])
{
vy[i] = 1;
if (! py[i])
{
aug (i); return ;
} else q.push (py[i]);
}
}
}
}
int d = linf;
rep (i, 1, n) if (! vy[i]) d = min (d, slack[i]);
rep (i, 1, n)
{
if (vx[i]) lx[i] -= d, sum -= d;
if (vy[i]) ly[i] += d, sum += d;
else slack[i] -= d;
}
rep (i, 1, n)
{
if (vy[i]) continue;
if(! slack[i])
{
vy[i] = 1;
if (! py[i])
{
aug (i); return ;
} else q.push (py[i]);
}
}
}
}
void solve ()
{
memset (lx, -127, sizeof lx);
sum = 0;
rep (i, 1, n) rep (j, 1, n) lx[i] = max (lx[i], e[i][j]);
rep (i, 1, n) sum += lx[i];
rep (i, 1, n)
bfs (i);
}
signed main ()
{
n = rd ();
rep (i, 1, n)
{
a[i] = rd (), b[i] = rd (), k[i] = rd ();
}
rep (i, 1, n)
rep (j, 1, n)
e[i][j] = max (0ll, a[i] - min (k[i], j - 1) * b[i]);
solve ();
printf ("%lld
", sum);
}
/*
*/
© 版权声明
文章版权归作者所有,未经允许请勿转载。
相关文章
暂无评论...