COCI 2017-2018#7 - Go

Solution

真的不会证这个的时间复杂度。。。

这道题有一个很关键的一点：当你向右或向左走时，中间的格子都会捉精灵。于是我们向右或向左时枚举步数从小到大，找到一个可以直接 \(break\) 掉，由下一个状态来扩展。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k, ans;
bool vis[105];
struct node {int id, v, t;} s[105];

bool cmp(const node a, const node b) {return a.id < b.id;}

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) < \'0\' || s > \'9\') if(s == \'-\') f = -1;
    while(s >= \'0\' && s <= \'9\') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

void dfs(const int dir, const int cur, const int sum, const int ti) {
    ans = max(ans, sum);
    for(int i = cur + dir; ~i && i <= m; i += dir)
        if(! vis[i] && abs(s[i].id - s[cur].id) + ti < s[i].t) {
            vis[i] = 1;
            dfs(1, i, sum + s[i].v, ti + abs(s[i].id - s[cur].id));
            dfs(-1, i, sum + s[i].v, ti + abs(s[i].id - s[cur].id));
            vis[i] = 0;
            break;
        }
}

int main() {
    n = read(), s[0].id = k = read(), m = read();
    for(int i = 1; i <= m; ++ i) s[i].id = read(), s[i].v = read(), s[i].t = read();
    sort(s, s + m + 1, cmp);
    for(int i = 0; i <= m; ++ i)
        if(s[i].id == k) {dfs(1, i, 0, 0); dfs(-1, i, 0, 0); break;}
    printf("%d\n", ans);
    return 0;
}