【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了~~

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

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 510
 8 #define INF 0xfffffff
 9 
10 int n;
11 int a[Maxn],mx[Maxn][Maxn],mn[Maxn][Maxn];
12 bool p[Maxn][Maxn];
13 int dp[Maxn][Maxn],f[Maxn],nt[Maxn],first[Maxn];
14 
15 int mymax(int x,int y) {return x>y?x:y;}
16 int mymin(int x,int y) {return x<y?x:y;}
17 
18 struct node
19 {
20     int id,x;
21 };//t[Maxn];
22 
23 bool cmp(node x,node y) {return x.x<y.x;}
24 
25 void init()
26 {
27     memset(first,0,sizeof(first));
28     memset(p,0,sizeof(p));
29     for(int i=1;i<=n;i++)
30     {
31         scanf("%d",&a[i]);
32         nt[i]=first[a[i]];first[a[i]]=i;
33     }
34     memset(mn,63,sizeof(mn));
35     for(int i=1;i<=n;i++) mx[i][i]=mn[i][i]=a[i],p[i][i]=1;
36     for(int i=n;i>=1;i--)
37       for(int j=i+1;j<=n;j++)
38       {
39           mx[i][j]=mymax(mx[i][j-1],a[j]);
40           mn[i][j]=mymin(mn[i][j-1],a[j]);
41           if(p[i][j-1]&&nt[j]<i) p[i][j]=1;
42       }
43 }
44 
45 int ddp(int x,int y)
46 {
47     if(dp[x][y]<10000) return dp[x][y];
48     if(x==y) {dp[x][y]=0;return 0;}
49     int num;
50     node t[Maxn];
51     for(int i=x;i<=y;i++) t[i-x+1].x=a[i],t[i-x+1].id=i;
52     sort(t+1,t+1+y-x+1,cmp);
53     for(int i=x;i<y;i++)
54     {
55         int mm=mymax(mn[x][i],mn[i+1][y]);
56         num=0;
57         for(int j=1;j<=y-x+1;j++)
58         {
59             if(t[j].x==mm) break;
60             if(t[j].x<mm) num++;
61         }
62         num=y-x+1-num;
63         dp[x][y]=mymin(dp[x][y],ddp(x,i)+ddp(i+1,y)+num);
64     }
65     return dp[x][y];
66 }
67 
68 void ffind()
69 {
70     memset(dp,63,sizeof(dp));
71     memset(f,63,sizeof(f));
72     for(int i=1;i<=n;i++)
73      for(int j=i;j<=n;j++)
74      {
75          if(mx[i][j]==j-i+1&&p[i][j]) 
76              ddp(i,j);
77      }
78     f[0]=0;
79     for(int i=1;i<=n;i++)
80      for(int j=0;j<i;j++) if(mx[j+1][i]==i-j&&p[j+1][i])
81      {
82          f[i]=mymin(f[i],f[j]+dp[j+1][i]);
83      }
84     if(f[n]>10000) printf("impossible
");
85     else printf("%d
",f[n]);
86 }
87 
88 int main()
89 {
90     while(scanf("%d",&n)!=EOF)
91     {
92         init();
93         ffind();
94     }
95     return 0;
96 }

uva1579

2016-03-08 13:32:04