- 科技
- P3146 [USACO16OPEN]248 G（dp，普及+提高）
题目：
分析：还是太菜，想不出来！
还是在想左右两部分在合并时的问题。
题解中引入了完全合并，即区间内必须是能合并到最后是一个数。
值得深入的想想。
代码：竟然T了：
#include<bits/stdc++.h>
using namespace std
;
int m
;
int A
[250];
int D
[250][250];
int maxx
=-1;
int f(int x
,int y
)
{
if(D
[x
][y
]!=-1) return D
[x
][y
];
if(x
==y
) return A
[x
];
if(x
+1==y
)
{
if(A
[x
]==A
[y
]) return A
[x
]+1;
return 0;
}
for(int i
=x
;i
<y
;i
++)
{
int c1
=f(x
,i
);
int c2
=f(i
+1,y
);
if(c1
==0||c2
==0) continue;
if(c1
==c2
)
{
D
[x
][y
]=max(D
[x
][y
],c1
+1);
}
}
return D
[x
][y
];
}
int main()
{
cin
>>m
;
for(int i
=0;i
<m
;i
++)
{
cin
>>A
[i
]; maxx
=max(maxx
,A
[i
]);
}
memset(D
,-1,sizeof(D
));
for(int i
=0;i
<m
-1;i
++)
for(int j
=i
+1;j
<m
;j
++)
{
maxx
=max(maxx
,f(i
,j
));
}
cout
<<maxx
;
}
题解：大概看了一下，确实可以吧！但感觉我写的递归也没到超时的地步，毕竟记忆化了。
Processed:
0.011, SQL:
8
