[USACO][Section 1.3][动态规划] Calf Flac

题目大意：

给出一个字符串（可能有多行），在只考虑字母的情况下（忽略大小写）找出一个最长的回文序列。

思路：

在程序最开始需要对数据进行预处理，提取字符串中的所有字母再全部转换为小写并存入进结构体序列tmp[]中，tmp[i].t表示字符串中第i个字母的小写形式。完成此题目需要动态规划的思想，分成两种情况考虑：

找出最长的奇数回文序列。需要用到一个辅助数组length[]。当tmp[i-length[i]-1].t==tmp[i+1].t时，length[i+1]=length[i]+2。

找出最长的偶数回文序列。同样用到辅助数组length[]。当tmp[i-length[i]].t==tmp[i+1].t时，length[i+1]=length[i]+2。

代码：

/*
ID: lujunda1
LANG: C++
PROG: calfflac
*/
#include
#include
#include
#include
#include 
using namespace std;
//words用来存储输入的原始数据
//tmp_words是在处理多行输入时用到的辅助数组 
char words[20001],tmp_words[20001];
//计算前需要对原始数据进行处理，仅保留字母（全部转换为小写）并记录每个字母在原始数据中的位置。 
struct point
{
    char t;
    int pos;
}tmp[20001];
//length数组用于记录当前位置所属回文序列的最大长度（实际因回文数列长度的奇偶性而有所差异） 
int length[20001];
//多行输入 
void input()
{
    words[0]='\0';
    while(gets(tmp_words))
    {
        int len=strlen(words); 
        //如果words长度不为0，则说明现在输入的不是第一行数据。 
        if(len)
        {
            //输入前，将“上一行”结尾的‘\0’改为‘\n’。 
            words[len]='\n';
            strcpy(words+len+1,tmp_words);
        }
        //如果words的长度为0，则说明现在正在输入第一行数据。 
        else
            strcpy(words,tmp_words);
    }
}
int main()
{
    freopen("calfflac.in","r",stdin);
    freopen("calfflac.out","w",stdout);
    input();
    //len用于记录处理过后的数据的长度。（所有字母的个数） 
    int len=0;
    for(int i=0,tmp_len=strlen(words);i='a'&&words[i]<='z')
        {
            tmp[len].pos=i;
            tmp[len++].t=words[i];
        }
        else if(words[i]>='A'&&words[i]<='Z')
        {
            tmp[len].pos=i;
            tmp[len++].t=words[i]-'A'+'a';
        }
    //下面代码是找出最大的奇数回文序列。
    //max_1表示最大的奇数回文序列长度
    //pos_1表示最大的奇数回文序列的最后一个字母所在位置 
    int max_1=0,pos_1=0;
    memset(length,0,sizeof(length));
    for(int i=0;i=0&&end=0&&endmax_2?max_1:max_2,pos=max_1>max_2?pos=pos_1:pos_2;
    printf("%d\n",max);
    for(int i=tmp[pos-max+1].pos;i<=tmp[pos].pos;i++)
        printf("%c",words[i]);
    printf("\n");
}