SRM439 div1 medium

メモ化再帰。
難しくて解説みた。

#include <string>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long LL;

LL DP[(1<<13)][2][15][15];

class PalindromePhrases 
{
	public:

		int n;
		vector<string> words;

		bool isPalindome(string s)
		{
			for(int i=0;i<s.size();i++)
				if(s[i]!=s[s.size()-1-i])
					return false;
			return true;
		}

		LL rec(int left,int isLeft,int id,int len)
		{
			LL &r=DP[left][isLeft][id][len];
			if(r!=-1)
				;
			else if(isLeft)
			{
				r=0;
				int pos=words[id].size()-len;
				string s=words[id].substr(pos);
				if(isPalindome(s))
					r++;
				for(int next=0;next<n;next++)
					if(left & (1<<next))
						if(len<words[next].size())
						{
							int i;
							for(i=0;i<len;i++)
								if(words[id][pos+i]!=words[next][words[next].size()-1-i])
									break;
							if(i==len)
								r+=rec(left^(1<<next),0,next,words[next].size()-i);
						}
						else
						{
							int i;
							for(i=0;i<words[next].size();i++)
								if(words[id][pos+i]!=words[next][words[next].size()-1-i])
									break;
							if(i==words[next].size())
								r+=rec(left^(1<<next),1,id,len-i);
						}
			}
			else
			{
				r=0;
				int pos=len-1;
				string s=words[id].substr(0,len);
				if(isPalindome(s))
					r++;
				for(int next=0;next<n;next++)
					if(left & (1<<next))
						if(len<words[next].size())
						{
							int i;
							for(i=0;i<len;i++)
								if(words[id][i]!=words[next][len-1-i])
									break;
							if(i==len)
								r+=rec(left^(1<<next),1,next,words[next].size()-i);
						}
						else
						{
							int i;
							for(i=0;i<words[next].size();i++)
								if(words[id][pos-i]!=words[next][i])
									break;
							if(i==words[next].size())
								r+=rec(left^(1<<next),0,id,len-i);
						}
			}
			return r;
		}

		LL getAmount(vector <string> _words) 
		{
			words=_words;
			n=words.size();

			memset(DP,-1,sizeof(DP));
			LL ans=0;
			for(int i=0;i<n;i++)
				ans+=rec(((1<<n)-1)^(1<<i),1,i,words[i].size());
			return ans;
		}
};