【題解】Kattis – Pokemon Go Go

【題目敘述】https://open.kattis.com/problems/pokemongogo

#include <iostream>
#include <map>
#include <cstring>
using namespace std;

int n, x[20], y[20], mn = 1e9, sz;
string s[20];
map <string, int> mp;
int dp[1<<20][20];

int get_id(int x){
    if (mp.count(s[x])) return mp[s[x]];
    else {
        return mp[s[x]] = mp.size();
    }
}

int dist(int a, int b){
    return abs(x[a]-x[b]) + abs(y[a]-y[b]);
}

int solve(int mask, int pos){
    if (~dp[mask][pos]) return dp[mask][pos];
    int mn = 1e9;
    if (__builtin_popcount(mask) == 1) return dp[mask][pos] = abs(x[pos]) + abs(y[pos]);
    for (int i = 0; i < n; i++){
        if (i == pos) continue;
        int x = get_id(i);
        if (x == get_id(pos)) continue;
        if ((mask & (1<<x)) == 0) continue;
        mn = min(mn, solve(mask ^ (1 << get_id(pos)), i) + dist(i, pos));
    }
    return dp[mask][pos] = mn;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x[i] >> y[i] >> s[i];
        get_id(i);
    }
    sz = mp.size();
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++){
        mn = min(mn, solve((1<<sz)-1, i) + abs(x[i]) + abs(y[i]));
    }
    cout << mn << "\n";
}
分享本文 Share with friends