UVa 11584 Partitioning by Palindromes 线性结构上dp LIS

UVa 11584 Partitioning by Palindromes 线性结构上dp LIS

The question is from here.

My Solution

d[ i ] = min{ d[ j ]+1 | is[j+1][i]是回文串 }; d[ i ] 表示0~i 内回文串的最小个数;

然后对于is[ j+1 ][ i ]是否为回文串要拿出来预处理好，枚举中心然后向两边延伸直到不同，且中心要分奇偶讨论;

偶数的两种情况其实是一样的; 且在最开始的时候也要 is[ i ][i+1] = 1， 别漏了;

#include 
#include 
#include 
//#define LOCAL
using namespace std;
char ch[1002];
int is[1002][1002],d[1002];

//!LIS

int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAL
    int T,len;
    scanf("%d", &T);
    while(T--){
        scanf("%s", ch);
        len = strlen(ch);

        memset(is,0,sizeof(is));
        //回文串 Palindrome 有两种情况的，包含单数个字符 和 包含偶数个字符
        for(int i = 0; i < len; i++){
            for(int j = i+1; j < len && 2*i-j >= 0; j++){
                if(ch[j] == ch[2*i-j]) is[2*i-j][j] = 1;
                else break;
            }
            if(ch[i] == ch[i+1] && i+1 < len){
                is[i][i+1] = 1;                                      //前面这里漏掉了，WA了两发。 注意边界别漏处理啊
                for(int j = i+2; j < len && i+i+1-j >= 0; j++){
                    if(ch[j] == ch[i+i+1-j]) is[i+i+1-j][j] = 1;
                    else break;
                }
            }
            /*else if(ch[i] == ch[i-1]){                             //这里和上面是一样的
                for(int j = i+1; j < len && i+i-1-j >= 0; j++){
                    if(ch[j] == ch[i+i-1-j]) is[i+i-1-j][j] = 1;
                    else break;
                }
            }*/
        }
        d[-1] = 0;
        for(int i = 0; i < len; i++){
            d[i] = d[i-1] + 1;
            for(int j = -1; j < i; j++){                             //! j 要从 -1 开始的，不然就不对了，因为下面要有 j+1
                if(is[j+1][i]) d[i] = min(d[i],d[j]+1);
            }
        }

        printf("%dn",d[len-1]);

    }
    return 0;
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx