首页 > 代码库 > poj3073

poj3073

  • 比赛状态堪忧,笑看自己找不着北..
  • 把心态放好吧- -
  • 反正窝从一開始就仅仅是为了多学习才上道的
  • 至少已经从学习和智商上给窝带来了一些帮助
  • 智商带不动,好辛苦~~~~(>_<)~~~~ 
  • 说说这题吧…这题就是个SB<script type="math/tex" id="MathJax-Element-2763">SB</script>题。考虑前i<script type="math/tex" id="MathJax-Element-2764">i</script>个字符能匹配的方案数。我们仅仅须要考虑它后几位是否能配上一组题目给出的字符就可以,于是有
    dp[i]=j=1ndp[j](if.[j,i])
    <script type="math/tex; mode=display" id="MathJax-Element-2765">dp[i]=\sum_{j=1}^{n}dp[j]\left(if. 字符[j,i]匹配上了某一组给定字符\right)</script>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 128 << 2;
int dp[MAX];
char rp[MAX >> 2][6] = 
{
    "4", "|3", "(", "|)", "3", "|=", "6", "#", "|",
    "_|", "|<", "|_", "|\\/|", "|\\|", "0", "|0", /*-P*/
    "(,)", "|?", "5", "7", "|_|", "\\/", "\\/\\/",
    "><", "-/", "2"
};

int main()
{
    char buffer[MAX];
    char s[MAX];
    while (cin >> buffer && buffer[0] != ‘e‘)
    {
        s[0] = ‘\0‘;
        int len = strlen(buffer);
        for (int i = 0; i < len; ++i)
        {
            strcat(s, rp[buffer[i] - ‘A‘]);
        }
        len = strlen(s);

        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < len; ++i)
        {
            char ch = s[i + 1];
            s[i + 1] = ‘\0‘;
            for (int t = 0; t < 26; ++t)
            {
                if (strcmp(rp[t], s) == 0)
                {
                    ++dp[i];
                    break;
                }
            }

            for (int j = 1; j <= i; ++j)
            {
                for (int t = 0; t < 26; ++t)
                {
                    if (strcmp(rp[t], s + j) == 0)
                    {
                        dp[i] += dp[j - 1];
                    }
                }
            }
            s[i + 1] = ch;
        }
        cout << dp[len - 1] << endl;
    }
    return 0;
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

poj3073