λC-day7

1.ak神
说是诈骗题，所以什么是诈骗题。
从条件里面可以看出来奇妙的东西，转变为取k+1,2k+1……nk+1的位置的数，然后就转变成了k=1的前后各取的题目，不完全理解为什么能保证最优策略。
2.tower
最开始找出来他是个签到，以为是个简单的dijkstra，真正跑的时候发现单单正常加边就把复杂度摁进地里摩擦了，后面转换成了边找路的同时便利点判断找边,倒是好了一点。
3.桌球
写过类似的选择题，一眼公式，然后由于思路不当塞了个Tn^2的复杂度进去，改了改变好了一点，20分，数组没法再大了。
4.你是？

下面是两块看一半的tower

void Add(int x, int y, int w = 0, int f = 0) {
    e[x].push_back(mp(y, w));
    if(f) e[y].push_back(mp(x, w));
}
#define get_l(x, t) ((x) + (t) * n) // 第t层点x的映射
void build() {
    // 1. 1至n层内部连边
    for(int i = 1; i <= k; i ++ )
        for(int j = 1; j <= n - 1; j ++ )
            Add(get_l(j, i), get_l(j + 1, i), 1, 1);
    // 2. 由第0层向其它层等效加边
    for(int i = 1; i <= n; i ++ ) Add(i, get_l(i, b[i]));
    // 3. 由其它层向第0层等效加边
    for(int i = 1; i <= k; i ++ )
        for(int j = 1; j <= n; j ++ )
            if(s[i][b[j]] == &#039;1&#039;) Add(get_l(j, i), j);
}
void work() {
#ifdef debug
    for(int i = 1; i <= get_l(n, k); i ++ ) {
        for_each(e[i].begin(), e[i].end(), [](PII x) -> void { cout << x.first << " "; });
        cout << endl;
    }
#endif
    memset(dist, 0x3f, sizeof dist);
    deque<int> Q;
    Q.push_back(1);
    dist[1] = 0;
    while(!Q.empty()) {
        int t = Q.front();
        Q.pop_front();
        for(unsigned i = 0; i < e[t].size(); i ++ ) {
            int u = e[t][i].first, w = e[t][i].second;
            if(dist[u] > dist[t] + w) {
                dist[u] = dist[t] + w;
                if(w) Q.push_back(u);
                else Q.push_front(u);
            }
        }
    }
    printf("%d\n", dist[n] > 1e9 ? -1 : dist[n]);
}

scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d",&col[i]);
    for(int i=1; i<=k; i++) {
        scanf("%s",str);
        for(int j=1; j<=k; j++)
            c[i][j]=(str[j-1]==&#039;1&#039;);
    }
    memset(f,0x3f,sizeof(f));
    f[0][1]=0;//走i步到j的最小代价 
    for(int i=1; i<=k; i++) {
        for(int j=1; j<=n; j++) {
            g[i][j]=c[col[j]][i];//j位置能否到达颜色i 
        }
    }
    for(int o=1; o<=k+k; o++) {
        if(o&1) {
            for(int i=1; i<=k; i++) {
                p[i]=INF;
                h[i]=0;
            }
            for(int j=1; j<=n; j++) {
                int cr=col[j];//第j点颜色 
                while(h[cr]<j) {//h[col[j]] 
                    h[cr]++;
                    if(g[cr][h[cr]])
                        p[cr]=min(p[cr],f[o-1][h[cr]]+n-h[cr]);
                }
                f[o][j]=min(f[o-1][j],p[cr]-n+j);
            }
        } else {
            for(int i=1; i<=k; i++) {
                p[i]=INF;
                h[i]=n+1;
            }
            for(int j=n; j>=1; j--) {
                int cr=col[j];
                while(h[cr]>j) {
                    h[cr]--;
                    if(g[cr][h[cr]])
                        p[cr]=min(p[cr],f[o-1][h[cr]]+h[cr]-1);
                }
                f[o][j]=min(f[o-1][j],p[cr]-j+1);
            }
        }
        res=min(res,f[o][n]);
    }
    if(res>n*k) printf("-1\n");
    else printf("%d\n",res);