吃奶酪
#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
double x, y;
} p[20];
double f[50000][16];
double dis(node a, node b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y;
}
int N = (1 << n) - 1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = 1e9;
}
}
for (int i = 1; i <= n; i++) {
f[1 << (i - 1)][i] = dis({0, 0}, p[i]);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= n; j++) {
if ((i & (1 << (j - 1))) == 0)
continue;
for (int k = 1; k <= n; k++) {
if (k == j)
continue;
if ((i & (1 << (k - 1))) == 0)
continue;
f[i][j] = min(f[i][j], f[i - (1 << (j - 1))][k] + dis(p[j], p[k]));
}
}
}
double res = 1e9;
for (int i = 1; i <= n; i++) {
res = min(res, f[N][i]);
}
cout << fixed << setprecision(2) << res << endl;
return 0;
}
互不侵犯
/*
f[i][j][k]第i行摆成j的状态，用了k个棋子的方法总数
f[i][j][k]+=f[i-1][s][k-need[j]]
need[i]摆成i这样的状态，需要多少个棋子
10101011
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, f[10][1024][82], need[1025], can[1025];
signed main() {
cin >> n >> m;
int N = (1 << n) - 1;
for (int i = 0; i <= N; i++) {
int x = i;
while (x) {
if (x % 2 == 1)
need[i]++;
x /= 2;
}
if ((i & (i >> 1)) == 0 && (i & (i << 1)) == 0)
can[i] = 1;
}
for (int i = 0; i <= N; i++) {
if (can[i] == 1) {
f[1][i][need[i]] = 1;
}
}
for (int i = 2; i <= n; i++) {
//枚举第i行的状态j
for (int j = 0; j <= N; j++) {
if (can[j] == 0)
continue;
//枚举上一行的状态s
for (int s = 0; s <= N; s++) {
if (can[s] == 0)
continue;
if ((s & j) != 0)
continue;
if ((j & (s << 1)) != 0)
continue;
if ((j & (s >> 1)) != 0)
continue;
//枚举用了棋子的总数
for (int l = m; l >= need[j]; l--) {
f[i][j][l] += f[i - 1][s][l - need[j]];
}
}
}
}
int res = 0;
for (int i = 0; i <= N; i++) {
res += f[n][i][m];
}
cout << res << endl;
return 0;
}
关灯问题II
#include <bits/stdc++.h>
using namespace std;
struct node {
int status, cost;
};
int n, m, a[105][11], book[1025];
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
queue<node>q;
book[(1 << n) - 1] = 1;
q.push({((1 << n) - 1), 0});
while (!q.empty()) {
node tmp = q.front();
q.pop();
if (tmp.status == 0) {
cout << tmp.cost << endl;
return 0;
}
for (int i = 1; i <= m; i++) {
int status = tmp.status;
for (int j = 1; j <= n; j++) {
if (a[i][j] == 0)
continue;
else if (a[i][j] == 1) {
if ((status & (1 << (j - 1))) != 0)
status -= (1 << (j - 1));
} else if (a[i][j] == -1) {
if ((status & (1 << (j - 1))) == 0)
status += (1 << (j - 1));
}
}
if (book[status] == 0) {
book[status] = 1;
q.push({status, tmp.cost + 1});
}
}
}
cout << -1 << endl;
return 0;
}
孤岛营救问题
#include <bits/stdc++.h>
using namespace std;
int n, m, p, k;
int can[11][11][11][11], s;
int key[11][11], nxt[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int book[11][11][1025];
struct node {
int x, y, key, cost;
};
//can[a][b][c][d] ab点到cd的墙的种类
int main() {
cin >> n >> m >> p >> k;
for (int i = 1; i <= k; i++) {
int x1, y1, x2, y2, g;
cin >> x1 >> y1 >> x2 >> y2 >> g;
if (g == 0) {
can[x1][y1][x2][y2] = -1;
can[x2][y2][x1][y1] = -1;
} else {
can[x1][y1][x2][y2] = g;
can[x2][y2][x1][y1] = g;
}
}
cin >> s;
for (int i = 1; i <= s; i++) {
int x, y, z;
cin >> x >> y >> z;
key[x][y] |= (1 << (z - 1));
}
queue<node>q;
q.push({1, 1, key[1][1], 0});
book[1][1][key[1][1]] = 1;
while (!q.empty()) {
node tmp = q.front();
q.pop();
if (tmp.x == n && tmp.y == m) {
cout << tmp.cost << endl;
return 0;
}
for (int i = 0; i < 4; i++) {
int nx = tmp.x + nxt[i][0];
int ny = tmp.y + nxt[i][1];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
if (can[tmp.x][tmp.y][nx][ny] == 0) {
int Key = tmp.key | key[nx][ny];
if (book[nx][ny][Key] == 0) {
book[nx][ny][Key] = 1;
q.push({nx, ny, Key, tmp.cost + 1});
}
} else {
if (can[tmp.x][tmp.y][nx][ny] == -1)
continue;
if ((tmp.key & (1 << (can[tmp.x][tmp.y][nx][ny] - 1))) == 0)
continue;
int Key = tmp.key | key[nx][ny];
if (book[nx][ny][Key] == 0) {
book[nx][ny][Key] = 1;
q.push({nx, ny, Key, tmp.cost + 1});
}
}
}
}
}
cout << -1 << endl;
return 0;
}
WIE
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n, m, p, k, dis[N][10005];
int key[N];
struct node {
int id, dis, key;
friend bool operator < (node a, node b) {
return a.dis > b.dis;
}
};
struct edge {
int v, w, monster;
};
vector<edge>e[N];
void dijkstra() {
memset(dis, 0x3f, sizeof(dis));
dis[1][key[1]] = 0;
priority_queue<node>q;
q.push((node) {
1, 0, key[1]
});
int res = 1e9;
while (!q.empty()) {
node tmp = q.top();
if (tmp.id == n) {
cout << tmp.dis << endl;
exit(0);
}
q.pop();
for (int i = 0; i < e[tmp.id].size(); i++) {
int v = e[tmp.id][i].v;
int w = e[tmp.id][i].w;
int monster = e[tmp.id][i].monster;
if ((tmp.key & monster) == monster) {
if (dis[v][tmp.key | key[v]] > tmp.dis + w) {
dis[v][tmp.key | key[v]] = tmp.dis + w;
q.push((node) {
v, dis[v][tmp.key | key[v]], tmp.key | key[v]
});
}
}
}
}
cout << -1 << endl;
}
int main() {
cin >> n >> m >> p >> k;
for (int i = 1; i <= k; i++) {
int x, t;
cin >> x >> t;
for (int j = 1; j <= t; j++) {
int c;
cin >> c;
key[x] |= (1 << (c - 1));
}
}
for (int i = 1; i <= m; i++) {
int x, y, z, t;
cin >> x >> y >> z >> t;
int monster = 0;
for (int j = 1; j <= t; j++) {
int c;
cin >> c;
monster |= (1 << (c - 1));
}
e[x].push_back((edge) {
y, z, monster
});
e[y].push_back((edge) {
x, z, monster
});
}
dijkstra();
return 0;
}
售货员的难题
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 21;
int n, a[N][N], f[1 << N][N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
memset(f, 0x3f, sizeof(f));
f[1][1] = 0;
for (int i = 1; i <= (1 << n) - 1; i++) {
for (int j = 1; j <= n; j++) {
if (i & (1 << (j - 1))) {
for (int k = 1; k <= n; k++) {
if (j != k) {
if (i & (1 << (k - 1))) {
f[i][j] = min(f[i][j], f[i - (1 << (j - 1))][k] + a[k][j]);
}
}
}
}
}
}
int res = 1e9;
for (int i = 1; i <= n; i++) {
res = min(f[(1 << n) - 1][i] + a[i][1], res);
}
cout << res;
return 0;
}
炮兵阵地
/*
f[i][j][k]
f[i][j][k] = max(f[i-1][k][s]+need(j))
*/
#include <bits/stdc++.h>
using namespace std;
int n, m, can[101][1025], need[1025], f[101][1025][1025];
int mat[101];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char x;
cin >> x;
if (x == 'P')
mat[i] |= (1 << (j - 1));
}
}
int N = (1 << m) - 1;
for (int i = 0; i <= N; i++) {
int x = i;
while (x) {
if (x % 2 == 1)
need[i]++;
x /= 2;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= N; j++) {
if ((j & (j << 1)) != 0)
continue;
if ((j & (j >> 1)) != 0)
continue;
if ((j & (j << 2)) != 0)
continue;
if ((j & (j >> 2)) != 0)
continue;
/*
10101110
00001111
*/
if ((mat[i] & j) != j)
continue;
can[i][j] = 1;
}
}
for (int i = 0; i <= N; i++) {
if (can[1][i] == 0)
continue;
for (int j = 0; j <= N; j++) {
if (can[2][j] == 0)
continue;
if ((i & j) != 0)
continue;
f[2][j][i] = need[i] + need[j];
}
}
for (int i = 3; i <= n; i++) {
for (int j = 0; j <= N; j++) {
if (can[i][j] == 0)
continue;
for (int k = 0; k <= N; k++) {
if (can[i - 1][k] == 0)
continue;
if ((j & k) != 0)
continue;
for (int s = 0; s <= N; s++) {
if (can[i - 2][s] == 0)
continue;
if ((s & k) != 0)
continue;
if ((s & j) != 0)
continue;
f[i][j][k] = max(f[i][j][k], f[i - 1][k][s] + need[j]);
}
}
}
}
int res = 0;
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
res = max(res, f[n][i][j]);
}
}
if(n!=1){
cout << res << endl;
}
else{
res = 0;
for(int i=0;i<=N;i++){
if(can[1][i]){
res = max(res,need[i]);
}
}
cout<<res<<endl;
}
return 0;
}
Corn Fields G
/*
f[i][j]第i行摆成j样子的方法总数
f[i][j]+=f[i-1][k]
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Mod = 1e8;
int n, m, can[15][5000];
int f[15][5000];
int mat[15];
signed main() {
cin >> n >> m;
int N = (1 << m) - 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x;
cin >> x;
if (x == 1) {
mat[i] |= (1 << (j - 1));
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= N; j++) {
if ((j & (j << 1)) != 0 || (j & (j >> 1)) != 0)
continue;
if ((mat[i] & j) != j)
continue;
can[i][j] = 1;
}
}
for (int i = 0; i <= N; i++) {
if (can[1][i] == 1)
f[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= N; j++) {
if (can[i][j] == 0)
continue;
for (int k = 0; k <= N; k++) {
if ((j & k) != 0)
continue;
if (can[i - 1][k] == 0)
continue;
f[i][j] += f[i - 1][k];
f[i][j]%=Mod;
}
}
}
int res = 0;
for (int i = 0; i <= N; i++) {
res += f[n][i];res%=Mod;
}
cout << res%Mod << endl;
return 0;
}
