zerol edited 7 年前
title: 【题解】EOJ - 卡车运输 (kamion)
date: 2017-11-30 14:48:02
categories: ACM
tags:
- dp
http://acm.ecnu.edu.cn/problem/3437/
有点复杂，请自行读题。
$$f[i][j][k]=\displaystyle \sum_{i \stackrel{type 1(X)}{\longrightarrow}a} \sum_{b \stackrel{type 2(x)}{\longrightarrow} j}g[a][b][k-2]$$
$$empty[i][j][k]=\displaystyle \sum_{t \stackrel{type 3}{\longrightarrow}j}empty[i][t][k-1]$$
$$g[i][j][k]=\displaystyle \sum_{t=1}^n \sum_{k’=0}^{k} g[i][t][k’] \times gg[t][j][k-k’] + empty[i][j][k]$$
$$gg[i][j][k]=\displaystyle \sum_{t=1}^n \sum_{k’=0}^{k} f[i][t][k’] \times empty[t][j][k-k’]$$
$$h[i][j][k]=\displaystyle \sum_{t=1}^n \sum_{k’=0}^{k} h[i][t][k’] \times f[t][j][k-k’] + \sum_{t \stackrel{type 1/3}{\longrightarrow} j}h[i][t][k-1]$$
由于只要求不超过 k 步，那么最后的答案为 $\sum_{k=0}^K h[1][n][k]$，复杂度 $O(n^5)$，由于我用的是邻接矩阵而非邻接表，所以常数会大一些。
搞了那么多状态转移方程，到底有什么必要呢？很遗憾，很可能是做复杂了。
这样做为什么是对的呢？由于转移的时候是枚举 中转站，所以必须保证对于特定的一种方案，只可能在某个特定的点作为中转站时被累加。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 50 + 5;
const int MOD = 10000 + 7;
int n, m, K;
int G[maxn][maxn];
int f[maxn][maxn][maxn], empty[maxn][maxn][maxn], g[maxn][maxn][maxn], h[maxn][maxn][maxn];
int gg[maxn][maxn][maxn];
inline void up(int& a, int b) { (a += b) %= MOD; }
int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
cin >> n >> m >> K;
int u, v;
char s[100];
FOR (_, 0, m) {
scanf("%d%d", &u, &v);
--u; --v;
gets(s);
if (strlen(s)) G[u][v] = s[1];
else G[u][v] = 1;
}
FOR (i, 0, n) h[i][i][0] = g[i][i][0] = empty[i][i][0] = 1;
FOR (k, 1, K + 1)
FOR (i, 0, n)
FOR (j, 0, n) {
if (k >= 2) FOR (a, 0, n) FOR (b, 0, n)
if (isupper(G[i][a]) && tolower(G[i][a]) == G[b][j])
up(f[i][j][k], g[a][b][k - 2]);
FOR (t, 0, n)
up(empty[i][j][k], empty[i][t][k - 1] * (G[t][j] == 1));
FOR (t, 0, n)
FOR (kk, 0, k + 1)
up(gg[i][j][k], f[i][t][kk] * empty[t][j][k - kk]);
FOR (t, 0, n)
FOR (kk, 0, k + 1)
up(g[i][j][k], g[i][t][kk] * gg[t][j][k - kk]);
up(g[i][j][k], empty[i][j][k]);
FOR (t, 0, n)
FOR (kk, 0, k + 1)
up(h[i][j][k], h[i][t][kk] * f[t][j][k - kk]);
FOR (t, 0, n)
up(h[i][j][k], (G[t][j] == 1 || isupper(G[t][j])) * h[i][t][k - 1]);
}
int ans = 0;
FOR (k, 0, K + 1) up(ans, h[0][n - 1][k]);
cout << ans << endl;
}
看不懂的标程
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 50
#define MAXK 50
#define MAXT 26
#define MOD 10007
#define ADD(a, b) a = (a + b) % MOD
#define FOR_EACH(it, cont) \
for(vector<par>::iterator it = cont.begin(); it != cont.end(); ++it)
int N, E, K;
typedef pair<int, int> par;
vector<par> road[MAXN];
vector<par> load[MAXN][MAXT];
vector<par> drop[MAXN][MAXT];
vector<par> road_plus_load[MAXN];
int dp[MAXK+1][MAXN][MAXN][2];
int helper[MAXK+1][MAXN][MAXN];
int main(void) {
char line[128];
scanf("%d%d%d", &N, &E, &K); gets(line);
for (int i = 0; i < E; ++i) {
int A, B;
char type;
gets(line);
int scanned = sscanf(line, "%d %d %c", &A, &B, &type); --A; --B;
if (scanned == 2) {
road[A].push_back(par(A, B));
road_plus_load[A].push_back(par(A, B));
} else if (isupper(type)) {
load[A][type - 'A'].push_back(par(A, B));
road_plus_load[A].push_back(par(A, B));
} else {
drop[B][type - 'a'].push_back(par(A, B));
}
}
for (int i = 0; i < N; ++i)
for (int flag = 0; flag < 2; ++flag)
dp[0][i][i][flag] = 1;
int ret = 0;
for (int k = 1; k <= K; ++k) {
if (k >= 2)
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int t = 0; t < MAXT; ++t)
FOR_EACH(it, load[i][t])
FOR_EACH(jt, drop[j][t])
ADD(helper[k][i][j], dp[k-2][it->second][jt->first][0]);
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int flag = 0; flag < 2; ++flag) {
vector<par> &roads = flag ? road_plus_load[i] : road[i];
FOR_EACH(it, roads)
ADD(dp[k][i][j][flag], dp[k-1][it->second][j][flag]);
for (int t = 2; t <= k; ++t)
for (int x = 0; x < N; ++x)
ADD(dp[k][i][j][flag], helper[t][i][x] * dp[k-t][x][j][flag]);
}
ADD(ret, dp[k][0][N-1][1]);
}
printf("%d\n", ret);
return 0;
}
看不懂的题解