洛谷P4283 [AHOI2008]Y型项链
? 解题记录 ? ? 洛谷 ? ? 模拟 ?    2018-10-21 14:51:59    486    0    0

题目描述

欢乐岛上众多新奇的游乐项目让小可可他们玩的非常开心。现在他们正在玩比赛串项链的游戏,谁串的最快就能得到优厚的奖品。

这可不是普通的项链,而是一种Y型项链,项链的最中间有一颗大珍珠作为结合点,从大珍珠上连出来3条由各种宝石串起来的链子。

比赛的规则是这样的:每次可以从三条链子中某一条的一端取下来一个宝石,或者安上去一个宝石,称为一次操作,经过若干次操作,最终使得三条链子完全相同。想要赢得比赛,那么只能使用尽量少的操作次数。

假设每种宝石都有无数多个以供使用,且链子足够长。你能帮助小可可赢得比赛吗?

注:由于对Y型项链的宝石数没有特殊的要求,所以即使你把所有宝石都取下来,也是一个可以接受的方案(三根没有串宝石的绳子也是完全一样的).

输入输出格式

输入格式:

 

一共有3行,表示Y型项链的三条链子,每行开始有一个数字N,表示初始时这条链子上串有N个宝石(N<=50),随后是一个空格,然后是N个'A'和'Z'之间的字符,表示这个链子上的宝石,每个字母表示一种不同的宝石,这个字符串最左边的字符表示的是离大珍珠最近的那个宝石,而最右边的表示的是在链子末端的宝石。

 

输出格式:

 

只有一个整数,表示所需要的最少的操作次数.

 

输入输出样例

输入样例#1: 复制
3 CAT
3 TAC
5 CATCH
输出样例#1: 复制
8

说明

提示:100%的数据中,N<=50.

50%的数据中,N<=20.

开始咸水题了qwq

显然最优决策会长成把三段字符串都切到某个位置然后补齐。

我们直接三重for循环枚举三个串分别被切到哪里对每一种方案求一下答案min一下就好了。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
char s[3][maxn];
int n[3], mx, ans = inf;

int check(int a, int b, int c) {
    int ans = 0, flag = 0, ml = max(a, max(b, c));
    for(register int i = 0; i <= ml; ++i) {
        flag = 0;
        if(i < a) flag = s[0][i];
        if(i < b) 
            if(flag) {if(flag != s[1][i]) return inf;}
            else flag = s[1][i];
        if(i < c) 
            if(flag) {if(flag != s[2][i]) return inf;}
    }
    return n[0] - a + n[1] - b + n[2] - c + 3 * ml - a - b - c;
}

int main() {
    for(register int i = 0; i < 3; ++i) {
        scanf("%d", &n[i]);
        scanf("%s", s[i]);
    }
    for(; s[0][mx] == s[1][mx] && s[1][mx] == s[2][mx]; ++mx);
    for(register int i = 0; i <= n[0]; ++i)
        for(register int j = 0; j <= n[1]; ++j)
            for(register int k = 0; k <= n[2]; ++k)
                ans = min(check(i, j, k), ans);
    printf("%d", ans);
    return 0;
}


上一篇: 洛谷P2039 [AHOI2009]跳棋

下一篇: 洛谷P3564 [POI2014]BAR-Salad Bar

486 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航