索鸟网

  1. 首页
  2. bzoj1055 [HAOI2008]玩具取名

bzoj1055 [HAOI2008]玩具取名


Description

某人有一套玩具,并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好,将名字中任意一个字母用“WING”中任意两个字母代替,使得自己的名字能够扩充得很长。现在,他想请你猜猜某一个很长的名字,最初可能是由哪几个字母变形过来的。
len200, W,I,N,G16

Solution

傻逼区间dp。然而我还看错题 + 数组开小调错20min。

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

inline int read() {
    int x = 0, flag = 1; char ch = getchar();
    while (ch > "9" || ch < "0") { if (ch == "-") flag = -1; ch = getchar(); }
    while (ch <= "9" && ch >= "0") { x = x * 10 + ch - "0"; ch = getchar(); }
    return x * flag;
}

#define N 201
#define rep(ii, aa, bb) for (int ii = aa; ii <= bb; ii++)
#define ll long long
const char chVal[] = { "?", "W", "I", "N", "G" };
char chKey[256];

int len;
int f[N][N][5];
int chgTot[5];
char chgWay[5][17][3];
char str[N];

int dp(int l, int r, int x) {
    if (l == r) return f[l][r][x] = (str[l] == chVal[x]);
    int &ans = f[l][r][x];
    if (ans != -1) return ans;
    rep(i, 1, chgTot[x]) rep(j, l, r - 1)
        if (dp(l, j, chKey[chgWay[x][i][1]]) && dp(j + 1, r, chKey[chgWay[x][i][2]]))
            return ans = 1;
    return ans = 0;
}

int main() {
    chKey["W"] = 1; chKey["I"] = 2; chKey["N"] = 3; chKey["G"] = 4;
    rep(i, 1, 4) scanf("%d", &chgTot[i]);
    rep(i, 1, 4) rep(j, 1, chgTot[i]) scanf("%s", chgWay[i][j] + 1);
    scanf("%s", str + 1); len = strlen(str + 1);
    bool flag = 0;
    memset(f, -1, sizeof f);
    rep(i, 1, 4) if (dp(1, len, i)) putchar(chVal[i]), flag = 1;
    if (!flag) puts("The name is wrong!");
    return 0;
}

来源地址:http://blog.csdn.net/aziint/article/details/78229903 版权归作者所有!

相关教程

  • BZOJ1055 玩具取名 [区间DP]

    1055: [HAOI2008]玩具取名Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2047  Solved: 1198[Submit][Status][Discuss]Description  某人有一套玩具,并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后 他会根据
  • BZOJ1054 移动玩具 [BFS][HASH]

    1054: [HAOI2008]移动玩具Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2407  Solved: 1345[Submit][Status][Discuss]Description  在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动 时只能将玩
  • BZOJ1054 移动玩具 [BFS][HASH]

    1054: [HAOI2008]移动玩具Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2407  Solved: 1345[Submit][Status][Discuss]Description  在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动 时只能将玩
  • [NOIP2017模拟]分玩具

    2017.10.11 T2 1968 样例数据 输入 3 1 3 1 输出 2 分析:又是一道O(n)题fffffffff!!!我的心理活动:第一眼,what?博弈论?NOIP要考这?你们既然极其聪明干嘛让我来算,不会,放弃。距考试结束40分钟时,打个暴力吧。距考试结束10分钟时,MMP连思路都没有写个屁屁。考完看题解,什么?DP
  • NOIP2017赛前模拟 分玩具

    Description: 豆豆和豆沙正在分一些玩具,每个玩具有一个好玩值,每个人可以拿走任意数量的玩具,获得的愉快度为最小的好玩值。现在豆豆先拿,每个人轮流操作,直到没有玩具可以拿。豆豆想知道他能比豆沙多出多少愉快度? Input: 第一行 N 表示玩具个数。 接下来一行 N 个整数表示第 i 个玩具的好玩值。 Output: 输出一个整数表示最多多出
  • NOIP模拟:分玩具(博弈论)

    豆豆和豆沙正在分一些玩具,每个玩具有一个好玩值,每个人可以拿走任意数量的玩具,获得的愉快度为最小的好玩值。现在豆豆先拿,每个人轮流操作,直到没有玩具可以拿。豆豆想知道他能比豆沙多出多少愉快度? 题解: 首先题意可以转化为一个有序数组分成n段分别加减加减依次进行,然后考虑dp,因为要满足最优子结构,所以从前往后用
  • bzoj1044: [HAOI2008]木棍分割(二分+单调队列)

    题目传送门 跑了3s那些200ms的是怎么跑出来的。。 解法: 第一问蛮简单。以前大概做过这种类型的题。。 就二分一下最长的那一段的长度。 然后O(n)判断一下。 第二问不简单。。 求方案诶。 我以前拿60分的时候打的是Dp。。 f[i][j]表示前i个分成j段切最长长度不大于第一问的答案的方案数。 那么继承就为f[k][j-1],k为上一段的结尾且满足k到i这一段木棍长度小于
  • [NOIP模拟][好题]分玩具

    题目描述: 豆豆和豆沙正在分一些玩具,每个玩具有一个好玩值,每个人可以拿走任意数量的玩具,获得的愉快度为最小的好玩值。现在豆豆先拿,每个人轮流操作,直到没有玩具可以拿。豆豆想知道他能比豆沙多出多少愉快度? 输入格式: 第一行 N 表示玩具个数。 接下来一行 N 个整数表示第 i 个玩具的好玩值。 输出格式: 输出一个整数表示最多多出的愉快度。 样例输入: 3 1 3 1