BZOJ3802 Vocabulary DP

yts1999 posted @ 2015年8月23日 23:00 in DP with tags DP bzoj , 644 阅读
这道题我在学校测试时当场A掉的。。。
一上来感觉好水。。。然后YY了一下:
p0 表示0串后面还有多少个?
p1 表示1串后面还有多少个?
p2 表示2串后面还有多少个?
{c} 表示满足c条件的方案数
f[0][0][k]:第k位之前三个串保证严格升序的方案数
f[0][1][k]:第k位之前0串和1串相同的方案数
f[1][2][k]:第k位之前1串和2串相同的方案数
f[0][2][k]:第k位之前三个串都相同的方案数
f[0][0][k]=26^(p0+p1+p2)
f[0][1][k]=f[0][1][k+1]*{a[0][k]==a[1][k]}+f[0][0][k+1]*{a[0][k]<a[1][k]}
f[1][2][k]=f[1][2][k+1]*{a[1][k]==a[2][k]}+f[0][0][k+1]*{a[1][k]<a[2][k]}
f[0][2][k]=f[0][2][k+1]*{a[0][k]==a[1][k]==a[2][k]}+f[0][1][k+1]*{a[0][k]==a[1][k]<a[2][k]}+f[1][2][k+1]*{a[0][k]<a[1][k]==a[2][k]}+f[0][0][k+1]*{a[0][k]<a[1][k]<a[2][k]}
ans=f[0][2][0]
就是这样。。。
然后代码200+行,一直改到最后提交前10分钟。。。
这是我写过的最长的代码了吧。。。
/**************************************************************
    Problem: 3802
    User: yts1999
    Language: C++
    Result: Accepted
    Time:2256 ms
    Memory:109676 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
 
const unsigned long long p = 131ull;
const long long mod = 1000000009ll;
 
long long bin[3000010];
char a[3][1000010];
int cnt[3][1000010];
long long f[3][3][1000010];
int len[3];
 
int main() {
    bin[0] = 1;
    for (int i = 1; i <= 3000000; i++)
        bin[i] = (bin[i - 1] * 26) % mod;
    int T;
    scanf("%d",&T);
    for (; T--;) {
        for (int i = 0; i < 3; i++) {
            scanf("%s",a[i]);
            len[i] = strlen(a[i]);
            cnt[i][len[i]] = 0;
            for (int j = len[i] - 1; j >= 0; j--)
                cnt[i][j] = cnt[i][j + 1] + (a[i][j] == '?');
        }
        int mx = max(len[0],max(len[1],len[2]));
        for (int i = 0; i < 3; i++) {
            for (int j = len[i]; j < mx; j++)
                a[i][j] = 'a' - 1;
            a[i][mx] = '\0';
        }
        f[0][0][mx] = 1;
        f[0][1][mx] = f[1][2][mx] = f[0][2][mx] = 0;
        for (int i = mx - 1; i >= 0; i--) {
            f[0][0][i] = bin[cnt[0][i] + cnt[1][i] + cnt[2][i]];
            //orz heheda
            long long p1 = 0;
            if (a[0][i] != '?' || a[1][i] != '?')
                if (a[0][i] != '?' && a[1][i] != '?' && a[0][i] != a[1][i])
                    p1 = 0;
                else
                    p1 = 1;
            else
                p1 = 26;
            p1 *= (a[2][i] == '?'?26:1);
            //orz heheda
            long long p2 = 0;
            if (a[0][i] != '?' || a[1][i] != '?')
                if (a[0][i] != '?' && a[1][i] != '?')
                    if (a[0][i] >= a[1][i])
                        p2 = 0;
                    else
                        p2 = 1;
                else
                    if (a[0][i] == '?')
                        if (a[1][i] == 'a' - 1)
                            p2 = 0;
                        else
                            p2 = a[1][i] - 'a';
                    else
                        p2 = 'z' - a[0][i];
            else
                p2 = 325;
            p2 *= (a[2][i] == '?'?26:1);
            f[0][1][i] = (f[0][1][i + 1] * p1 % mod + f[0][0][i + 1] * p2 % mod) % mod;
            //orz heheda
            p1 = 0;
            if (a[1][i] != '?' || a[2][i] != '?')
                if (a[1][i] != '?' && a[2][i] != '?' && a[1][i] != a[2][i])
                    p1 = 0;
                else
                    p1 = 1;
            else
                p1 = 26;
            p1 *= (a[0][i] == '?'?26:1);
            //orz heheda
            p2 = 0;
            if (a[1][i] != '?' || a[2][i] != '?')
                if (a[1][i] != '?' && a[2][i] != '?')
                    if (a[1][i] >= a[2][i])
                        p2 = 0;
                    else
                        p2 = 1;
                else
                    if (a[1][i] == '?')
                        if (a[2][i] == 'a' - 1)
                            p2 = 0;
                        else
                            p2 = a[2][i] - 'a';
                    else
                        p2 = 'z' - a[1][i];
            else
                p2 = 325;
            p2 *= (a[0][i] == '?'?26:1);
            f[1][2][i] = (f[1][2][i + 1] * p1 % mod + f[0][0][i + 1] * p2 % mod) % mod;
            //orz heheda
            p1 = 0;
            if (a[0][i] != '?' || a[1][i] != '?' || a[2][i] != '?')
                if (a[0][i] != '?')
                    if ((a[1][i] != '?' && a[0][i] != a[1][i]) || (a[2][i] != '?' && a[0][i] != a[2][i]))
                        p1 = 0;
                    else
                        p1 = 1;
                else
                    if (a[1][i] != '?')
                        if (a[2][i] != '?' && a[1][i] != a[2][i])
                            p1 = 0;
                        else
                            p1 = 1;
                    else
                        p1 = 1;
            else
                p1 = 26;
            //orz heheda
            p2 = 0;
            if (a[0][i] != '?' || a[1][i] != '?')
                if (a[0][i] != '?' && a[1][i] != '?')
                    if (a[0][i] != a[1][i])
                        p2 = 0;
                    else
                        if (a[2][i] == '?')
                            p2 = 'z' - a[0][i];
                        else
                            if (a[0][i] >= a[2][i])
                                p2 = 0;
                            else
                                p2 = 1;
                else
                    if (a[0][i] != '?')
                        if (a[2][i] != '?')
                            if (a[0][i] >= a[2][i])
                                p2 = 0;
                            else
                                p2 = 1;
                        else
                            if (a[0][i] == 'a' - 1)
                                p2 = 0;
                            else
                                p2 = 'z' - a[0][i];
                    else
                        if (a[2][i] != '?')
                            if (a[1][i] >= a[2][i])
                                p2 = 0;
                            else
                                p2 = 1;
                        else
                            if (a[1][i] == 'a' - 1)
                                p2 = 0;
                            else
                                p2 = 'z' - a[1][i];
            else
                if (a[2][i] != '?')
                    if (a[2][i] == 'a' - 1)
                        p2 = 0;
                    else
                        p2 = a[2][i] - 'a';
                else
                    p2 = 325;
            //orz heheda
            long long p3 = 0;
            if (a[1][i] != 'a' - 1 && a[2][i] != 'a' - 1)
                if (a[1][i] != '?' || a[2][i] != '?')
                    if (a[1][i] != '?' && a[2][i] != '?')
                        if (a[1][i] != a[2][i])
                            p3 = 0;
                        else
                            if (a[0][i] == '?')
                                p3 = a[1][i] - 'a';
                            else
                                if (a[0][i] >= a[1][i])
                                    p3 = 0;
                                else
                                    p3 = 1;
                    else
                        if (a[1][i] != '?')
                            if (a[0][i] != '?')
                                if (a[0][i] >= a[1][i])
                                    p3 = 0;
                                else
                                    p3 = 1;
                            else
                                p3 = a[1][i] - 'a';
                        else
                            if (a[0][i] != '?')
                                if (a[0][i] >= a[2][i])
                                    p3 = 0;
                                else
                                    p3 = 1;
                            else
                                p3 = a[2][i] - 'a';
                else
                    if (a[0][i] != '?')
                        p3 = 'z' - a[0][i];
                    else
                        p3 = 325;
            else
                p3 = 0;
            //orz heheda
            long long p4 = 0;
            if (a[1][i] != 'a' - 1 && a[2][i] != 'a' - 1)
                if ((a[0][i] != '?' && a[1][i] != '?' && a[0][i] >= a[1][i]) || (a[0][i] != '?' && a[2][i] != '?' && a[0][i] >= a[2][i]) || (a[1][i] != '?' && a[2][i] != '?' && a[1][i] >= a[2][i]))
                    p4 = 0;
                else
                    if (a[0][i] != '?' && a[1][i] != '?' && a[2][i] != '?')
                        p4 = 1;
                    else
                        if (a[0][i] != '?')
                            if (a[1][i] == '?' && a[2][i] == '?')
                                p4 = ((int)('z' - a[0][i])) * ((int)('z' - a[0][i] - 1)) / 2;
                            else
                                if (a[1][i] != '?')
                                    p4 = 'z' - a[1][i];
                                else
                                    p4 = a[2][i] - a[0][i] - 1;
                        else
                            if (a[1][i] != '?')
                                if (a[2][i] != '?')
                                    p4 = a[1][i] - 'a';
                                else
                                    p4 = ((int)(a[1][i] - 'a')) * ((int)('z' - a[1][i]));
                            else
                                if (a[2][i] != '?')
                                    p4 = ((int)(a[2][i] - 'a')) * ((int)(a[2][i] - 'a' - 1)) / 2;
                                else
                                    p4 = 2600;
            else
                p4 = 0;
            f[0][2][i] = ((f[0][2][i + 1] * p1 % mod + f[0][1][i + 1] * p2 % mod) % mod + (f[1][2][i + 1] * p3 % mod + f[0][0][i + 1] * p4 % mod) % mod) % mod;
        }
        printf("%lld\n",f[0][2][0]);
    }
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter