C 撕书III-3 SRM 09

背景&&描述

    琉璃双在撕书。

    书总共有n页，每页都可以看作是一个数字。

    琉璃读书喜欢来回地读。但他也因此发现了作者的灌水行为：有些连续的若干页正着读和倒着读完全一样，也就是说是回文的。

    发生这种情况时，琉璃会非常地angry，把那些书页给撕掉。

    汀捡到了本黑色的魔法书。因为担心杀死书后会带来麻烦，决定借琉璃的手把书处置掉。

    大概就是每次选出剩余书页中的一个回文子串，拿给琉璃看....

    汀比较懒，他想知道最少选多少次就能让琉璃把整本书都撕光。

    注意，撕完一段之后会导致原本不相邻的两页变得相邻。

 

输入格式

    第一行一个整数n，表示书的页数。

    第二行为n个数字。

输出格式

    一个整数，表示最少选多少次。

样例输入

71 4 4 2 3 2 1

样例输出

2

数据范围与约定

• 对于100%的数据:，n个数字均为小于等于n的正整数。

样例解释

    先撕掉第2,3页，然后把剩下的直接撕掉。

来源

cf原题

————————————————————————————————

dp还是太弱啊

枚举长度 f【i】【j】表示从i——j撕掉这一段所需要的次数

如果s【i】==s【j】 f【i】【j】可以从f【i+1】【j-1】转移过来

当然还要枚举端点判断是否有更优的情况

#include
      
       #include
       
        #include
        
         using namespace std;const int M=507,inf=0x3f3f3f3f; int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n;int f[M][M],s[M];int main(){    n=read();    for(int i=1;i<=n;i++) s[i]=read();    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=inf;    for(int i=1;i<=n;i++) f[i][i]=1;    for(int i=1;i