【题解】剪纸条(dp)

HRBUST - 1828

网上搜不到题解？那我就来写一篇吧哈哈哈

最优化问题先考虑\(dp\)，设\(dp(i)\)表示将前\(i\)个字符(包括\(i\))分割成不相交的回文子串的最小数目

直接模拟题意转移即可。初始化写在里面了，\(dp(i)=i\)

其中\(S[j\dots i]\)是一个回文串，\(O(n^2)\)预处理回文串即可，注意偶回文串和奇回文串。

刚开始想太多，这道题。以后遇最优化的题一定要花有一定量的时间设计DP，因为DP的操作性强，正确性也比较好验证，即使后面有其他的解法，DP也可以作为对拍的保障。

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e2+5;

char c[maxn];

int dp[maxn],in[maxn][maxn],n;

int main(){

      c[0]='_';

      while(~scanf("%s",c+1)){

	    n=strlen(c+1);

	    for(register int t=1;t<=n;++t)

		  for(register int i=1;i<=n;++i)

			in[t][i]=0;

	    for(register int t=1;t<=n;++t){

		  register int p=0;

		  while(c[t-p]==c[t+p]) in[t-p][t+p]=1,++p;

		  p=0;

		  while(c[t-p]==c[t+1+p]) in[t-p][t+1+p]=1,++p;

		  dp[t]=t;

	    }

	    for(register int t=1;t<=n;++t)

		  for(register int i=1;i<=t;++i)

			if(in[i][t])

			      dp[t]=min(dp[t],dp[i-1]+1);

	    printf("%d\n",dp[n]-1);

      }

      return 0;

}