Algoogle

Algorithm for Programming Contest

LiveArchive 4336 Palindromic paths

Category: LiveArchive Tag: dp

Palindromic paths

問題概要


N(2<=N<=50)頂点のグラフがある.
頂点番号を0からN-1まで割り当てるとき,頂点の組について番号の小さい方の頂点から大きい方の頂点へ1文字のラベル付きの辺が張られている.
0からN-1までのパスを考える時,ラベルを順に並べて回文になるもののうち最長のものを求めよ.
複数ある場合は辞書順最小のものを求めよ.

解法


DPする.
パスの両端の頂点を近づけていく感じ.
dp[u][v] := 頂点0からu,頂点N-1からvまで進んだ時の最長の文字列
更新はuから進む辺とvから戻る辺をみて,同じラベルの辺があったらそれを加えて縮める.
答えの更新は,辺(u,v)のラベルと今の文字列の反転を加えたものでする.
u,vが同じならそのまま反転したものを加える.

コード


(4336.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

int n, used[64][53];
string dp[64][64], f[64], ans;

void update(int u, int v)
{
        string tmp = dp[u][v];
        string tmp2 = tmp;
        reverse(tmp2.begin(),tmp2.end());
        if(u == v) tmp += tmp2;
        else {
                tmp.push_back(f[u][v]);
                tmp += tmp2;
        }
        if(tmp.size() > ans.size()) ans = tmp;
        else if(tmp.size() == ans.size() and tmp < ans) ans = tmp;
}

string solve()
{
        ans = "";
        used[0][n-1] = 1;
        for (int i = 0; i < n; i++) {
                for (int j = n-1; j >= i; j--) {
                        if(!used[i][j]) continue;
                        update(i,j);
                        for (int ni = i+1; ni < n; ni++) {
                                for (int nj = j-1; nj >= ni; nj--) {
                                        if(f[i][ni] != f[nj][j]) continue;
                                        string tmp = dp[i][j];
                                        tmp.push_back(f[i][ni]);
                                        if(!used[ni][nj] or dp[ni][nj].size() < tmp.size() or
                                           (dp[ni][nj].size() == tmp.size() and tmp < dp[ni][nj])) {
                                                used[ni][nj] = 1;
                                                dp[ni][nj] = tmp;
                                        }
                                }
                        }
                }
        }
        return ans;
}

void init()
{
        memset(used,0,sizeof(used));
        for (int i = 0; i < 64; i++) {
                for (int j = 0; j < 64; j++) {
                        dp[i][j] = "";
                }
        }
}

void input()
{
        init();
        cin >> n;
        for (int i = 0; i < n; i++) cin >> f[i];
}

int main()
{
        int T; cin >> T;
        while(T--) {
                input();
                cout << solve() << endl;
        }
        return 0;
}

Comments