codeforces D.Palindrome pairs動的計画

ちょうど道题を书くことを始めます私はただ1つのnの4回の方のアルゴリズムを思い付いて打つ勇気がありません!!!その後、磊兄と議論してn二次方程式のアルゴリズムを得ることはできます.
1 iを末尾ノードとする回文個数dp 1[i]を算出し、iを先頭ノードとする個数dp 2[i]を算出することで、乗算さえすればよいというn方、
前処理dp 1[i],dp 2[i]もn方のアルゴリズム详しくコードを见ましょう!!!

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char a[2005];
long long dps[2005],dpe[2005];
int main()
{
    while(~scanf("%s",&a))
    {
        int len=strlen(a);
        for(int i=0;i<=len;i++)
        {
            dps[i]=dpe[i]=1;
        }
        for(int i=0;i<len;i++)//     
        {
            for(int j=0;j<(len/2+1);j++)
            {
                if((i-j)<0||(i+j+1)>=len)
                break;
                if(a[i-j]==a[i+1+j])
                {
                    dps[i-j]++;
                    dpe[i+1+j]++;
                }
                else
                break;
            }
        }
        for(int i=1;i<len;i++)  //     
        {
            for(int j=1;j<(len/2+1);j++)
            {
                if((i-j)<0||(i+j)>=len)
                break;
                if(a[i-j]==a[i+j])
                {
                    dps[i-j]++;
                    dpe[i+j]++;
                }
                else
                break;
            }
        }
        long long ans=0;
        for(int i=0;i<len;i++)
        {
            long long sum=0;
            for(int j=i+1;j<len;j++)
            sum+=dps[j];
            ans+=sum*dpe[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}