卡车运输

zerol edited 1 年,1 月前


title: 【题解】EOJ - 卡车运输 (kamion)
date: 2017-11-30 14:48:02
categories: ACM
tags:
- dp


题目

http://acm.ecnu.edu.cn/problem/3437/

题意

有点复杂,请自行读题。

题解

#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;
}

看不懂的题解

Comments

你正在回复博客
存在问题!