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

Expecto · 2016-09-30 13:31:30 · 题解

记忆化搜索简单易懂。

RT，用map存一个字符串的方案数，每次四种情况累加起来

#include<bits/stdc++.h>
using namespace std;
string s;
map<string,int> f;
int find(string x){
    if (f[x]!=0) return f[x];
    int tmp=1;
    int l=x.size();
    for (int i=1;i*2<l;i++){
        if (x.substr(0,i)==x.substr(l-i,i)) 
            tmp+=find(x.substr(i,l-i))+find(x.substr(0,l-i));
        if (x.substr(0,i)==x.substr(i,i))
            tmp+=find(x.substr(i,l-i));
        if (x.substr(l-2*i,i)==x.substr(l-i,i)) 
            tmp+=find(x.substr(0,l-i));
    }
    return f[x]=tmp%2014;
}
int main(){
    cin>>s;
    cout<<(find(s)+2014-1)%2014;
    return 0;
}