BLACKBOARD BONANZA

Alice and Bob both have lots of candies but want more. They decide to play the following turn-based game.

First they write some words on a few pieces of paper and put them into a bag so they cannot see the words. Next they decide whose turn is first. The first turn begins with the first player drawing and keeping a piece of paper with the word A from the bag and copying A onto a blackboard evenly spaced.

Then the second player draws and keeps a piece of paper with the word B on it. The current player is to write B on the blackboard underneath A evenly spaced. The second player receives one candy from the first for each character that matches vertically between A and B.

Now it is the first player’s turn who similarly draws and places word C underneath B and gains a candy for each of the characters vertically matched between B and C. The game continues until there are no more words in the bag.

What is the maximum number of candies that one of Alice and Bob can possibly get in a turn?

The game on the second blackboard awards the second player one candy. The game on the third blackboard awards the second player two candies.

Program Input

The first line of the input contains an integer t (1 ≤ t ≤ 70), the number of test cases. Each test case starts with an integer n (2 ≤ n ≤ 70), the number of words in the bag. Then follow n lines containing one word each (in no particular order). Each word will contain between 1 and 70 characters, all of them uppercase letters of English alphabet.

Program Output

For each test case, print a line containing the maximum number of candies either Alice or Bob can get in a single turn.

Sample Input & Output

INPUT

2
2
ALICE
BOB
2
ABCB
BCAB

OUTPUT

0
2

Calgary Collegiate Programming Contest 2008

題目要我們找到兩個字串作為遊戲時，最多的分數。
而這個分數來自於所有可能的對照方式，計算 match 的字元個數(可以不連續)。
只有硬爆一途。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char s[105][105];
int slen[105];
int calc(char a[], char b[]) {
    int i, j, k, ret = 0, cnt;
    for(i = 0; a[i]; i++) {
        cnt = 0;
        for(j = 0, k = i; b[j] && a[k]; j++, k++)
            if(a[k] == b[j])
                cnt++;
        ret = max(ret, cnt);

    }
    return ret;
}
int main() {
    int testcase;
    int n, i, j;

    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%s", &s[i]);
            slen[i] = strlen(s[i]);
        }
        int ans = 0;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                if(i == j) continue;
                if(slen[i] <= ans || slen[j] <= ans)
                    continue;
                int tmp = calc(s[i], s[j]);
                ans = max(ans, tmp);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

我要檢舉

#11548#Blackboard Bonanza

台長： Morris

您可能對以下文章有興趣

[UVA][time] 12136 - Schedule of a Married Man

[ZJ版本][dp] d524. Q10599 - Robots(II)

[UVA][sssp] 658 - It's not a Bug, it's a Feature!

a247. Fermat vs. Pythagoras

人氣(682) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][dfs、剪枝] 10890 - Maze
此分類上一篇:[UVA][dp] 11545 - Avoiding Jungle in the Dark

回應(0)