P6883 [COCI2016-2017中哪道题的解题思路最独特？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1159个文字，预计阅读时间需要5分钟。
状态压缩+DP+好题。题目描述：Mislav有+N个玻璃杯，从(1~N)编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子中），使这些杯子中只有+K个有水‘。
状压 DP 好题。
题目描述Mislav 有 \(N\) 个玻璃杯，从 \(1\sim N\) 编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子），使这些杯子中只有 \(K\) 个有水。
已知将第 \(i\) 号玻璃杯中的水倒入第 \(j\) 号，需要消耗 \(C_{i,j}\) 的代价。Mislav 想知道，经过倒水后满足只有 \(K\) 个（或更少）玻璃杯中有水时，消耗的代价总和的最小值。
\(1\le K\le N\le 20\)。
大体思路由于每个水杯只有有水和没水两个状态，并且可以证明，由于一开始所有杯子都有水，操作过程中有水的杯子 \(i\) 不会把水倒到没水的杯子 \(j\)。这是因为如果 \(j\) 不倒出，\(i\to j\) 不会使得有水的杯子数减少；如果 \(j\) 最终倒出，应该在 \(j\) 变成空杯子前进行操作。
所以，本题可以使用状压 DP 进行计算。将 \(N\) 个杯子有无水的状态用 \(N\) 位二进制数 \(S\) 表示，\(f_S\) 表示状态为 \(S\) 时的最小代价。初始 \(f_{111...1}=0\)，其余 \(f=\infty\)。
转移时，从大到小枚举 \(S\)，每次取 \(S\) 的二进制为 \(1\) 的位置 \(p,k\)，满足 \(p\neq k\)，则 \(p\) 号杯子为空的状态可能是由 \(S\) 转移过去，将 \(p\) 倒入 \(k\) 中。由此可得状态转移方程为 f[S-(1<<p)]=min{f[S]+c[p][k]}。
统计的答案为所有 \(1\) 的个数不超过 \(K\) 的状态 \(S\) 中 \(\min\{f_S\}\)。时间复杂度 \(O(2^NN^2)\)，\(N=20\) 时约为 \(O(419430400)\)。然而，事实上时间复杂度小于此。
对于二进制中有 \(t\) 个 \(1\)，枚举 \(p,k\) 的复杂度为 \(O(t^2)\)，而这样的状态有 \(\binom N t\) 个。由恒等变换 \(t\binom N t=N\binom{N-1}{t-1}\) 可得总的计算次数是为
所以时间复杂度为 \(O(N(N+1)2^{N-2})\)，当 \(N=20\) 时约为 \(O(10^8)\) 刚好可过。
完整代码#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> PII;
const int maxn = 5 + (1 << 20);
const ll inf = 0x3f3f3f3f;
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char _buf[1<<21], *p1 = _buf, *p2 = _buf;
template <typename T>
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template <typename T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template <typename T>
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
ll pop_cnt[maxn], c[21][21], f[maxn], N, K;
ll ans;
int main () {
ans = inf;
memset(f, inf, sizeof f);
read(N); read(K);
f[(1ll << N) - 1] = 0;
rep(i, 0, N - 1)
rep(j, 0, N - 1)
read(c[i][j]);
for(ll p = 1; p < (1ll << N); p ++)
pop_cnt[p] = pop_cnt[p >> 1] + (p & 1);
for(ll S = (1ll << N) - 1; S >= 1; S --) {
rep(p, 0, N - 1) if((S >> p) & 1) {
rep(k, 0, N - 1) if(((S >> k) & 1) && p != k)
f[S - (1ll << p)] = min(f[S - (1ll << p)], f[S] + c[p][k]);
}
if(pop_cnt[S] <= K) ans = min(ans, f[S]);
}
writeln(ans);
return 0;
}
本文共计1159个文字，预计阅读时间需要5分钟。
状态压缩+DP+好题。题目描述：Mislav有+N个玻璃杯，从(1~N)编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子中），使这些杯子中只有+K个有水‘。
状压 DP 好题。
题目描述Mislav 有 \(N\) 个玻璃杯，从 \(1\sim N\) 编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子），使这些杯子中只有 \(K\) 个有水。
已知将第 \(i\) 号玻璃杯中的水倒入第 \(j\) 号，需要消耗 \(C_{i,j}\) 的代价。Mislav 想知道，经过倒水后满足只有 \(K\) 个（或更少）玻璃杯中有水时，消耗的代价总和的最小值。
\(1\le K\le N\le 20\)。
大体思路由于每个水杯只有有水和没水两个状态，并且可以证明，由于一开始所有杯子都有水，操作过程中有水的杯子 \(i\) 不会把水倒到没水的杯子 \(j\)。这是因为如果 \(j\) 不倒出，\(i\to j\) 不会使得有水的杯子数减少；如果 \(j\) 最终倒出，应该在 \(j\) 变成空杯子前进行操作。
所以，本题可以使用状压 DP 进行计算。将 \(N\) 个杯子有无水的状态用 \(N\) 位二进制数 \(S\) 表示，\(f_S\) 表示状态为 \(S\) 时的最小代价。初始 \(f_{111...1}=0\)，其余 \(f=\infty\)。
转移时，从大到小枚举 \(S\)，每次取 \(S\) 的二进制为 \(1\) 的位置 \(p,k\)，满足 \(p\neq k\)，则 \(p\) 号杯子为空的状态可能是由 \(S\) 转移过去，将 \(p\) 倒入 \(k\) 中。由此可得状态转移方程为 f[S-(1<<p)]=min{f[S]+c[p][k]}。
统计的答案为所有 \(1\) 的个数不超过 \(K\) 的状态 \(S\) 中 \(\min\{f_S\}\)。时间复杂度 \(O(2^NN^2)\)，\(N=20\) 时约为 \(O(419430400)\)。然而，事实上时间复杂度小于此。
对于二进制中有 \(t\) 个 \(1\)，枚举 \(p,k\) 的复杂度为 \(O(t^2)\)，而这样的状态有 \(\binom N t\) 个。由恒等变换 \(t\binom N t=N\binom{N-1}{t-1}\) 可得总的计算次数是为
所以时间复杂度为 \(O(N(N+1)2^{N-2})\)，当 \(N=20\) 时约为 \(O(10^8)\) 刚好可过。
完整代码#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> PII;
const int maxn = 5 + (1 << 20);
const ll inf = 0x3f3f3f3f;
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char _buf[1<<21], *p1 = _buf, *p2 = _buf;
template <typename T>
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template <typename T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template <typename T>
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
ll pop_cnt[maxn], c[21][21], f[maxn], N, K;
ll ans;
int main () {
ans = inf;
memset(f, inf, sizeof f);
read(N); read(K);
f[(1ll << N) - 1] = 0;
rep(i, 0, N - 1)
rep(j, 0, N - 1)
read(c[i][j]);
for(ll p = 1; p < (1ll << N); p ++)
pop_cnt[p] = pop_cnt[p >> 1] + (p & 1);
for(ll S = (1ll << N) - 1; S >= 1; S --) {
rep(p, 0, N - 1) if((S >> p) & 1) {
rep(k, 0, N - 1) if(((S >> k) & 1) && p != k)
f[S - (1ll << p)] = min(f[S - (1ll << p)], f[S] + c[p][k]);
}
if(pop_cnt[S] <= K) ans = min(ans, f[S]);
}
writeln(ans);
return 0;
}