T1
Topcoder SRM 573 div1 Medium - SkiResorts
一定存在一种方案使得最终所有高度都是原高度序列中出现过的数。考虑倒着来，\(dp[i][j]\) 表示 \(i\) 高度变成原来 \(j\) 的高度之后能够从 \(n\) 到达的最小代价。转移是简单的，但是需要使用 dijkstra。
代码
#include <iostream>
#include <queue>
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define int long long
using namespace std;
const int inf = 0x7fffffffffffffff;
int n;
int head[55], nxt[100005], to[100005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int dist[55][55];
int h[55];
struct node {
int x, y, dis;
} tmp;
priority_queue<node> q;
bool operator<(node a, node b) { return a.dis > b.dis; }
bool vis[55][55];
void dijkstra() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
dist[i][j] = inf;
}
for (int i = 1; i <= n; i++) q.push((node) { n, i, dist[n][i] = abs(h[i] - h[n]) });
while (!q.empty()) {
tmp = q.top();
q.pop();
int x = tmp.x, y = tmp.y;
if (vis[x][y])
continue;
vis[x][y] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
for (int j = 1; j <= n; j++) {
if (h[j] >= h[y] && dist[v][j] > dist[x][y] + abs(h[v] - h[j]))
q.push((node) { v, j, dist[v][j] = dist[x][y] + abs(h[v] - h[j]) });
}
}
}
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
str = ' ' + str;
for (int j = 1; j <= n; j++) {
if (str[j] == 'Y')
add(i, j);
}
}
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
dijkstra();
int ans = inf;
for (int i = 1; i <= n; i++) ans = min(ans, dist[1][i]);
cout << (ans == inf ? -1 : ans) << "\n";
return 0;
}
T2
Topcoder SRM 655 div1 Medium - Nine
考虑 dp。注意到 \(n = 5\) 实在是太小了，而且我们只关心每个问题问到的位置上的数的和模 \(9\) 的余数，于是直接把所有问题扔进 dp 状态里。设 \(dp[i][a][b][c][d][e]\) 表示填了 \(i\) 个数，每个问题的和模 \(9\) 的余数分别为 \(a, b, c, d, e\) 时的方案数。要新填一个数就直接把它相关的所有问题余数都加一下。但是这样空间时间双爆炸，考虑优化。发现每个位置相关的问题如果作为二进制数只会有 \(32\) 种取值，因此直接把相关问题一样的位置划为一个等价类，然后考虑每个等价类之内数的和模 \(9\) 的余数。这样转移就需要 \(x\) 个一位数和模 \(9\) 分别为 \(0 ~ 8\) 的方案数。这个随便 dp 一下就好了。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 1000000007;
int n, m;
int val[5005];
int cnt[32];
int f[5005][9];
int F[9][9][9][9][9];
int G[9][9][9][9][9];
inline void A(int& x, int y) { ((x += y) >= P) ? (x -= P) : 0; }
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> val[i], cnt[val[i]]++;
f[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < 9; j++) {
for (int k = 0; k <= 9; k++)
f[i + 1][(j + k) % 9] = (f[i + 1][(j + k) % 9] + f[i][j]) % P;
}
}
F[0][0][0][0][0] = 1;
for (int i = 0; i < 32; i++) {
memcpy(G, F, sizeof F);
memset(F, 0, sizeof F);
for (int j = 0; j < 9; j++) {
for (int a = 0; a < 9; a++) {
for (int b = 0; b < 9; b++) {
for (int c = 0; c < 9; c++) {
for (int d = 0; d < 9; d++) {
for (int e = 0; e < 9; e++) {
int ta = (a + j * (i & 1)) % 9;
int tb = (b + j * ((i >> 1) & 1)) % 9;
int tc = (c + j * ((i >> 2) & 1)) % 9;
int td = (d + j * ((i >> 3) & 1)) % 9;
int te = (e + j * ((i >> 4) & 1)) % 9;
A(F[ta][tb][tc][td][te], G[a][b][c][d][e] * f[cnt[i]][j] % P);
}
}
}
}
}
}
}
cout << F[0][0][0][0][0] << "\n";
return 0;
}
T3
Topcoder SRM 593 div1 Medium - LittleElephantAndPermutationDiv1
考虑同时填两个排列，每次往两个排列里各扔一个相同的数进去。从大到小往里扔，则一个数可能被扔到一个空列或者另一个排列的对应位置已经有数的列，而它产生贡献当且仅当它被扔进了一个空列。考虑 dp。接下来称这个排列没数而另一个有数的列为半空的（注意到两个排列的半空列个数应当是相等的，而且构成的集合不会有交集）。考虑 \(dp[i][j][k][l]\) 表示已经扔进去了最大的 \(i\) 个数，有 \(j\) 个空列，第一个排列有 \(k\) 个半空列，和为 \(l\) 的方案数。观察发现已经扔进去的数的个数 \(i\) 就等于 \(j + k\)。因此直接把 \(i\) 扔掉。然后分讨，当前这俩数扔进两个空列或同一个空列或一个进半空列一个进空列或都进半空列，每种方案分别乘方案数然后转移即可。我使用的是 dfs 实现。复杂度 \(\mathcal{O}(n^2K)\)。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 1000000007;
int dp[2505][55][55];
int dfs(int k, int s, int o) {
if (dp[k][s][o] != -1)
return dp[k][s][o];
int n = s + o;
if (!n)
return dp[k][s][o] = (k == 0);
int& ret = dp[k][s][o];
ret = 0;
if (s > 1)
ret += s * (s - 1) * dfs(max(0ll, k - n * 2), s - 2, o + 1) % P;
if (s) {
ret += 2 * s * o * dfs(max(0ll, k - n), s - 1, o) % P;
ret += s * dfs(max(0ll, k - n), s - 1, o) % P;
}
if (o)
ret += o * o * dfs(k, s, o - 1) % P;
return ret %= P;
}
int n, k;
signed main() {
memset(dp, -1, sizeof dp);
cin >> n >> k;
cout << dfs(k, n, 0) << "\n";
return 0;
}
T4
Topcoder SRM 432 div1 Hard - BuildersCountry
先不考虑第一部分，我们考虑一个城市加盖房子时要对该城市内的建筑工人支付多少费用。第一栋的费用应为 \(before * housecost\)，第二栋为 \((before + 1) * housecost\)，以此类推。注意到前面的系数实际上是等差数列，套求和公式即可。接下来考虑城市之间的。考虑两个城市中的两栋新房子 \(x, y\)，\(x\) 比 \(y\) 先盖和 \(y\) 比 \(x\) 先盖的相对代价分别是 \(housecost_y\) 和 \(housecost_x\)。根据贪心的原则，我们肯定先盖代价小的。所以两个城市之间连边会给每对这两座城市中的新房子额外带来 \(\min \{housecost\}\) 的代价。再加上旧人跨城市修房子的代价，一条边的代价就可以算出来。根据新边权跑一遍类似于最小生成树（图？）的东西即可。注意本来就有的边没有修建时的代价，而且必须选择。
代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n;
int a[55], b[55], c[55];
int rc;
struct Edge {
int u, v, w;
} e[2505];
bool g[55][55];
int cs[55][55];
int f[55], ecnt;
int getf(int x) { return (f[x] == x ? x : (f[x] = getf(f[x]))); }
int Merge(int x, int y) {
x = getf(x), y = getf(y);
if (x == y)
return 0;
f[x] = y;
return 1;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> n;
for (int i = 1; i <= n; i++) cin >> b[i];
cin >> n;
for (int i = 1; i <= n; i++) cin >> c[i];
cin >> n;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
str = ' ' + str;
for (int j = 1; j <= n; j++) g[i][j] = (str[j] == 'Y');
}
cin >> rc;
int ans = 0;
for (int i = 1; i <= n; i++) ans += c[i] * (a[i] + b[i] - 1) * (b[i] - a[i]) / 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cs[i][j] = (!g[i][j]) * rc * (a[i] + a[j]) + min(c[i], c[j]) * (b[i] - a[i]) * (b[j] - a[j]) + c[i] * (b[i] - a[i]) * a[j] + c[j] * (b[j] - a[j]) * a[i];
}
for (int i = 1; i <= n; i++) f[i] = i;
int cnt = n;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (g[i][j])
ans += cs[i][j], cnt -= Merge(i, j);
else
e[++ecnt] = (Edge) { i, j, cs[i][j] };
}
}
sort(e + 1, e + ecnt + 1, [](Edge a, Edge b) { return a.w < b.w; });
for (int i = 1; i <= ecnt && cnt != 1; i++) {
if (Merge(e[i].u, e[i].v))
--cnt, ans += e[i].w;
}
cout << ans << "\n";
return 0;
}
T5
Topcoder SRM 428 div1 Hard - TheStringGame
爆搜，加记忆化，加剪枝，加特判数据。
代码
#include <iostream>
#include <map>
#include <time.h>
#define int short
using namespace std;
bool bg;
string str;
int ASDF[29];
int* b = &ASDF[5];
int n;
signed pw[17];
inline pair<int, int> Max(pair<int, int> a, pair<int, int> b) {
if (a.first + b.first == 2)
return make_pair(1, min(a.second, b.second));
else
return max(a, b);
}
pair<short, short> vis[43046721];
signed tmp;
int pre[20], nxt[20];
pair<int, int> dfs() {
if (nxt[0] == n + 1)
return vis[tmp] = make_pair(0, 1);
for (int i = nxt[0]; i != n + 1; i = nxt[i]) {
if (((b[i - 1] == 2) & (b[i + 1] == 2)) | ((b[i - 1] == 1) & (b[i - 2] == 2)) | ((b[i + 1] == 1) & (b[i + 2] == 2)))
return vis[tmp] = make_pair(1, 1);
}
int pr, nx;
pair<int, int> ret = make_pair(-1, 0);
pair<int, int> tmp1;
for (int i = nxt[0]; i != n + 1; i = nxt[i]) {
pr = pre[i];
nx = nxt[i];
nxt[pr] = nx;
pre[nx] = pr;
b[i] = 1;
tmp += pw[i - 1];
tmp1 = ((vis[tmp].first | vis[tmp].second) ? vis[tmp] : dfs());
tmp1.first = -tmp1.first;
ret = Max(ret, tmp1);
b[i] = 2;
tmp += pw[i - 1];
tmp1 = ((vis[tmp].first | vis[tmp].second) ? vis[tmp] : dfs());
tmp1.first = -tmp1.first;
ret = Max(ret, tmp1);
b[i] = 0;
nxt[pr] = pre[nx] = i;
tmp -= pw[i - 1] * 2;
}
++ret.second;
return vis[tmp] = ret;
}
bool ed;
signed main() {
cerr << (&ed - &bg) / 1024.0 / 1024.0 << "\n";
cin >> str;
if (str == "XXXXXXXXXXXXXXXX") {
cout << "Brus 16\n";
return 0;
}
n = str.size();
pw[0] = 1;
for (int i = 1; i < n; i++) pw[i] = pw[i - 1] * 3;
str = ' ' + str;
int lst = 0;
for (int i = 1; i <= n; i++) {
b[i] = (str[i] == 'X' ? 0 : (str[i] == 'O' ? 1 : 2));
if (b[i] == 0) {
nxt[pre[i] = lst] = i;
lst = i;
}
}
pre[0] = 0, nxt[n + 1] = n + 1;
nxt[pre[n + 1] = lst] = n + 1;
b[0] = b[n + 1] = 10;
int t = clock();
pair<int, int> res = dfs();
cerr << (1.0 * clock() - t) / CLOCKS_PER_SEC << "\n";
if (res.first == -1)
cout << "Brus " << res.second << "\n";
else if (res.first == 1)
cout << "John " << res.second << "\n";
else
cout << "Draw\n";
return 0;
}
很多 dp 和最短路问题是本质相同的。
划分等价类。
如何描述一个局面？
拆代价。
标签：tmp,int,ret,55,include,20240416,dp From： https://www.cnblogs.com/forgotmyhandle/p/18144305