Hướng dẫn giải của Trại đông Bảo Lộc 2021 - Giao hàng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Gọi ~dp[i][cap][last][mask]~ là thời gian ngắn nhất khi xét đến xe thứ i, lượng hàng còn được phép giao là ~cap~, đỉnh vừa thăm là ~last~ và cần phải giao cho các đỉnh thuộc tập ~mask~.
- Trạng thái xuất phát: ~dp[1][Q][0][\{1, 2, 3, \dots, n\}]~
- Trường hợp 1: Chuyển xe, chuyển sang trạng thái ~dp[i+1][Q][0][mask]~, thời gian tăng thêm ~c[last][0]~ do xe thứ ~i~ di chuyển từ đỉnh ~last~ về depot (~0~).
- Trường hợp 2: Đi tiếp, chuyển sang trạng thái ~dp[i][cap-d[next]][next][mask \setminus \{next\}]~, thời gian tăng thêm ~c[last][next]~, với ~next \in mask~ và ~cap - d[next] \geq 0~.
- Trạng thái kết thúc: ~dp[K][cap][last][0] = 0~
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) x.rbegin(), x.rend()
#define reu(i, a, b) for(ll i = (a); i <= (b); ++i)
#define red(i, a, b) for(ll i = (a); i >= (b); --i)
#define deb(x) cout << #x << ": " << x << "\n"
#define deb2(x, y) cout << #x << ": " << x << ", " << #y << ": " << y << "\n"
#define clr(x) memset(x, 0, sizeof x)
#define PI 3.141592653589793238
#define pb push_back
#define mp make_pair
#define F first
#define S second
template<typename T> inline void read(T &x) {
x = 0; char c;
while (!isdigit(c = getchar()));
do x = x*10 + c-'0';
while (isdigit(c = getchar()));
}
template<typename T> inline void write(T x) {
if (x > 9) write(x/10);
putchar(x%10 + '0');
}
typedef int64_t ll;
typedef deque<int> di;
typedef deque<ll> dll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pll> vpll;
typedef vector<pii> vii;
typedef tuple<ll,ll,ll> iii;
ll inp() {
ll x = 0; char c;
while (!isdigit(c = getchar()));
do x = x*10 + c-'0';
while (isdigit(c = getchar()));
return x;
}
string inp_str() {string x; cin >> x; return x;}
void fast_io() {ios::sync_with_stdio(0); cin.tie(0);}
void print_bool(bool a, string t = "YES", string f = "NO") {
if (a) cout << t << "\n";
else cout << f << "\n";
}
/***Main Code***/
#define DEBUG 0
#define FILE_IO 0
const ll N = 13, K = 10, maxQ = 23;
ll n, k, c[N][N], Q, d[N];
ll dp[K][maxQ][N][1<<N];
const ll INF = 1e18;
ll allBits = 0;
void Input() {
cin >> n >> k >> Q;
reu(i, 1, n) cin >> d[i];
reu(i, 0, n) reu(j, 0, n) cin >> c[i][j];
}
void minimize(ll &a, ll b) {
if (a > b) a = b;
}
bool have(ll v, ll t) {return (t >> v) & 1;}
void Solve() {
allBits = (1<<n)-1;
red(i, k, 0)
reu(q, 0, Q)
reu(u, 0, n)
red(t, allBits, 0) {
ll &res = dp[i][q][u][t];
res = INF;
if (i == k) {
if (t == allBits) res = 0;
else res = INF;
} else {
res = INF;
if (q < Q) minimize(res, dp[i+1][Q][0][t] + c[u][0]);
reu(v, 1, n) {
if (q - d[v] < 0 || have(v-1, t)) continue;
minimize(res, dp[i][q-d[v]][v][t|(1<<(v-1))] + c[u][v]);
}
}
}
ll ans = dp[0][Q][0][0];
write(ans);
}
int main()
{
fast_io();
Input(), Solve();
return 0;
}
Bình luận