题解 P3102 【[USACO14FEB]秘密代码Secret Code】

chenxinyang2006 · 2019-10-09 18:57:57 · 题解

本题解适合有想法，但是掉坑的人。完全不会的别看

这题是个神仙题

本题有两个大坑：

1、不能不删字符，也就是ABA无法变到ABAABA

2、方案数一开始应该为1，表示这个子串一开始有1种方案（即它本身，不变换），但是你应该输出经过变换后的方案，所以还要-1

（但是我很好奇，直接-1不会因为%2014后方案为0，然后输出-1而去世？果然USACO太水了）

然后就可以了，不过我真的想膜拜不看题解一遍AC的人，这两个坑基本上都会掉一个，而且如果两个都有（写初值赋0、可以不删字符的版本）在样例还会负负得正

code：

#include <cstdio>
#include <cstring>
using namespace std;
int n;
char str[105];
int dp[105][105];

bool pre(int s1,int e1,int s2,int e2){
    for(int i = 0;i <= (e2 - s2);i++){
        if(str[s1 + i] != str[s2 + i]){
            return 0;
        }
    }
    return 1;
}

bool las(int s1,int e1,int s2,int e2){
    for(int i = 0;i <= (e2 - s2);i++){
        if(str[e1 - (e2 - s2) + i] != str[s2 + i]){
            return 0;
        }
    }
    return 1;
}

int main(){
    scanf("%s",str + 1);
    n = strlen(str + 1);
    for(int i = 1;i <= n;i++){
        dp[i][i + 1] = 1;
    }
    for(int len = 3;len <= n;len++){
        for(int i = 1;i <= n;i++){
            int j = i + len - 1;
            if(j > n){
                break;
            }
            dp[i][j] = 1;
            for(int k = i;k < j;k++){
                if((k - i + 1) > (j - k)){
                    if(pre(i,k,k + 1,j)){
                        dp[i][j] = (dp[i][j] + dp[i][k]) % 2014;
                    }
                    if(las(i,k,k + 1,j)){
                        dp[i][j] = (dp[i][j] + dp[i][k]) % 2014;
                    }
                }
                if((k - i + 1) < (j - k)){
                    if(pre(k + 1,j,i,k)){
                        dp[i][j] = (dp[i][j] + dp[k + 1][j]) % 2014;
                    }
                    if(las(k + 1,j,i,k)){
                        dp[i][j] = (dp[i][j] + dp[k + 1][j]) % 2014;
                    }
                }
            }
        }
    }
    printf("%d\n",dp[1][n] - 1);
    return 0;
}

最后说一下，本代码是可以卡成n ^ 4的，但是USACO数据比较弱智，所以过了