这道题应该是dp(有点空洞)我们想，f(i)表示前i个套娃合并成多个套娃组所应操作的最小次数
f(i)=min(f(j)+dp(j+1,i));
这里自然的引出了dp(j+1,i)什么是dp(j+1,i)呢？
dp(j+1,i)合并成一个套娃所拥有的最小代价。
这里又不自然的dp(j+1,i)=min{dp(j+1,k)+dp(k,i)+操作数}
那么操作数又是什么呢，
对于要合并的两个区间[l,k]&[k+1,r]，最后一步把他们合并的费用是多少呢？假设m1=min[l,k],m2=min[k+1,r],则不用打开的套娃数为这个区间中小于max（m1,m2）的数的个数。
问题完美解决。
#include<cstdio> #include<cstring> #include<algorithm> #define N 500+10 #define inf 0x3fffffff using namespace std; int a[N],mx[N][N],mn[N][N],p[N][N]; int n; int f1[N][N],f2[N]; struct node{ int x,id; inline bool operator < (const node & a)const{return x<a.x;} }; void init() { memset(mx,0,sizeof(mx));memset(mn,63,sizeof(mn)); memset(p,0,sizeof(p)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++)mn[i][i]=mx[i][i]=a[i],p[i][i]=1; int flag; for(int i=n;i>=1;i--) for(int j=i+1;j<=n;j++) { mx[i][j]=max(mx[i][j-1],a[j]); mn[i][j]=min(mn[i][j-1],a[j]); flag=1; for(int k=j-1;k>=i;k--) { if(a[k]==a[j]){flag=0;break;} } if(flag&&p[i][j-1])p[i][j]=1; } // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) // { // printf("%d %d %d ",i,j,p[i][j]); // } } int dp(int x,int y) { if(f1[x][y]<10000) return f1[x][y]; if(x==y){return f1[x][y]=0;} int num; node t[N]; for(int i=x;i<=y;i++)t[i-x+1].x=a[i],t[i-x+1].id=i; sort(t+1,t+1+y-x+1); for(int i=x;i<y;i++) { int mm=max(mn[x][i],mn[i+1][y]); num=0; for(int j=1;j<=y-x+1;j++) { if(t[j].x==mm) break; if(t[j].x<mm) num++; } num=y-x+1-num; f1[x][y]=min(f1[x][y],dp(x,i)+dp(i+1,y)+num); } return f1[x][y]; } void slove() { memset(f1,63,sizeof(f1)); memset(f2,63,sizeof(f2)); // for(int i=1;i<=n;i++) // for(int j=i;j<=n;j++) // { // if(mx[i][j]==j-i+1&&p[i][j]) // printf("%d %d %d ",i,j,dp(i,j)); // } f2[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) { if(p[j+1][i]&&i-j==mx[j+1][i]) f2[i]=min(f2[i],f2[j]+dp(j+1,i)); // printf("%d %d %d ",j+1,i,dp(j+1,i)); } if(f2[n]>10000)printf("impossible "); else printf("%d ",f2[n]); } int main() { while(scanf("%d",&n)==1) { init(); slove(); } return 0; }
p[i][j]表示i——j这段区间是否有重复的元素，小技巧p[i][j]=(p[i][j-1]&&a[j]!=任何i————j-1的数）