【UVA1579】俄罗斯套娃 Matryoshka (动态规划)

题目：

　　

分析：

　　其实就是两个dp结合起来。第一个dp求区间[l,r]全部合并起来要用的最小次数，可以用区间[l,k]&[k+1,r]转移(l<=k<r)。第二个dp求前i个娃娃分成多个套娃组最小合并次数。这两个动态规划都是很常规的。

　　我们考虑一个问题：怎样的区间才能弄成一个套娃组（即为1~p的互不相同的数）呢？其实只要保证这个区间的数互不相同且max值为len即可。

　　对于要合并的两个区间[l,k]&[k+1,r]，最后一步把他们合并的费用是多少呢？假设m1=min[l,k],m2=min[k+1,r],则不用打开的套娃数为这个区间中小于max（m1,m2）的数的个数。（这个也很好理解）

　　然而我想不到很好的处理的方法，本题数据规模是n<=500，总感觉会超时，然而却AC了~~

代码如下：（有点恶心~~~）

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 510

 #define INF 0xfffffff

 int n;

 int a[Maxn],mx[Maxn][Maxn],mn[Maxn][Maxn];

 bool p[Maxn][Maxn];

 int dp[Maxn][Maxn],f[Maxn],nt[Maxn],first[Maxn];

 int mymax(int x,int y) {return x>y?x:y;}

 int mymin(int x,int y) {return x<y?x:y;}

 struct node

 {

     int id,x;

 };//t[Maxn];

 bool cmp(node x,node y) {return x.x<y.x;}

 void init()

 {

     memset(first,,sizeof(first));

     memset(p,,sizeof(p));

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

     {

         scanf("%d",&a[i]);

         nt[i]=first[a[i]];first[a[i]]=i;

     }

     memset(mn,,sizeof(mn));

     for(int i=;i<=n;i++) mx[i][i]=mn[i][i]=a[i],p[i][i]=;

     for(int i=n;i>=;i--)

       for(int j=i+;j<=n;j++)

       {

           mx[i][j]=mymax(mx[i][j-],a[j]);

           mn[i][j]=mymin(mn[i][j-],a[j]);

           if(p[i][j-]&&nt[j]<i) p[i][j]=;

       }

 }

 int ddp(int x,int y)

 {

     if(dp[x][y]<) return dp[x][y];

     if(x==y) {dp[x][y]=;return ;}

     int num;

     node t[Maxn];

     for(int i=x;i<=y;i++) t[i-x+].x=a[i],t[i-x+].id=i;

     sort(t+,t++y-x+,cmp);

     for(int i=x;i<y;i++)

     {

         int mm=mymax(mn[x][i],mn[i+][y]);

         num=;

         for(int j=;j<=y-x+;j++)

         {

             if(t[j].x==mm) break;

             if(t[j].x<mm) num++;

         }

         num=y-x+-num;

         dp[x][y]=mymin(dp[x][y],ddp(x,i)+ddp(i+,y)+num);

     }

     return dp[x][y];

 }

 void ffind()

 {

     memset(dp,,sizeof(dp));

     memset(f,,sizeof(f));

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

      for(int j=i;j<=n;j++)

      {

          if(mx[i][j]==j-i+&&p[i][j])

              ddp(i,j);

      }

     f[]=;

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

      for(int j=;j<i;j++) if(mx[j+][i]==i-j&&p[j+][i])

      {

          f[i]=mymin(f[i],f[j]+dp[j+][i]);

      }

     if(f[n]>) printf("impossible\n");

     else printf("%d\n",f[n]);

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         init();

         ffind();

     }

     return ;

 }

uva1579

2016-03-08 13:32:04