[CodeForces159D]Palindrome pairs[dp]

제목 링크: [CodeForces 159D] Palindrome pairs[dp]
제목 분석: s[a..b]s[x.y] & & a<=b
문제풀이 사고방식: 이 문제는DP의 사상을 채택하여 두 개의 수조를 설정한다. 그것이 바로 dpr[i]와 dpl[i]이다.
ppl[i] 대표: i로 시작하는 회문 문자열 개수;ppr[i] 대표: i를 끝으로 하는 회문 문자열 개수;
a,b는 a,b만 만족시키기 때문에
구체적인 코드는 다음과 같습니다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
    int dpl[2015],dpr[2015]; //dpl[i]: i        dpr[i]: i      ; ：   str[dpl,dpr]
    string str;
    while (cin >> str)
    {
        unsigned long long length = str.size();
        memset(dpr,0,sizeof(dpr));
        memset(dpl,0,sizeof(dpl));
        for (int i = 0; i < length; ++i)
        {
            for (int r = i, l = i; r < length && l >= 0 && str[l] == str[r]; ++r, --l)
            dpl[l]++,dpr[r]++; //    
            for (int r = i + 1, l = i; r < length && l >= 0 && str[l] == str[r]; ++r, --l)
            dpl[l]++,dpr[r]++; //    
        }
        for (int i = 1; i < length; ++i)
            dpr[i] += dpr[i-1];  //   dpr[i]    ：    i   str[a..b]     
        long long sum = 0;
        for (int i = 1; i < length; ++i)
            sum += dpr[i-1]*dpl[i];
        cout << sum << endl;
    }
    return 0;
}