Editorial for Trại đông Bảo Lộc 2021 - Giao hàng
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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;
}
Comments