P3146 [USACO16OPEN]248 & P3147 [USACO16OPEN]262144

注:两道题目题意是一样的,但是数据范围不同,一个为弱化版,另一个为强化版。

P3146传送门(弱化版)

思路:

  区间动规,设 f [ i ][ j ] 表示在区间 i ~ j 中获得的最大值,与普通区间动规最大的不同在于:只有左区间的最大值等于右区间的最大值时才能够进行转移。

AC代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define maxn 257
int n;
int maxx=-0x3f;//maxx记录合并后的最大值
int f[maxn][maxn];//f[i][j]表示 i~j 区间内合并后的最大值
inline int read()
{
char kr=;
char ls;
for(;ls>''||ls<'';kr=ls,ls=getchar());
int xs=;
for(;ls>=''&&ls<='';ls=getchar())
{
xs=xs*+ls-;
}
if(kr=='-') xs=-xs;
return xs;
}
int main()
{
n=read();
for(int i=;i<=n;i++)
{
f[i][i]=read();
maxx=max(f[i][i],maxx);
}
for(int i=;i<=n;i++)// i 枚举区间长度
{
for(int j=;j+i-<=n;j++)//枚举左端点
{
int r=i+j-;//计算出右端点
for(int k=j;k<r;k++)//枚举断点
{
if(f[j][k]==f[k+][r])//如果断点的左右两边最大值相等,转移
{
f[j][r]=max(f[j][r],f[j][k]+);
maxx=max(maxx,f[j][r]);//记录最大值
}
}
}
}
printf("%d\n",maxx);//输出
return ;
}

P3147传送门(强化版)

思路:

  在数据范围 2~262144 的情况下,使用区间动规在空间和时间上就有点吃不消了。这是我们考虑更加优化的动规,可以设 f [ i ][ j ] 表示从 j 开始合并到 i 这个数字序列的末尾的下标是什么。那么因为合并的总是一段连续的区间,就有 f [ i ][ j ] = f [ i-1 ][ f [ i-1 ][ j ] ];

AC代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define maxn 300000
int n,a;
int ans=-0x3f;
int f[][maxn];
inline int read()
{
char kr=;
char ls;
for(;ls>''||ls<'';kr=ls,ls=getchar());
int xs=;
for(;ls>=''&&ls<='';ls=getchar())
{
xs=(xs<<)+(xs<<)+ls-;
}
if(kr=='-') xs=-xs;
return xs;
}
int main()
{
n=read();
for(int i=;i<=n;i++)
{
a=read();
f[a][i]=i+;
}
for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
{
if(!f[i][j]) f[i][j]=f[i-][f[i-][j]];
if(f[i][j]) ans=i;
}
}
printf("%d\n",ans);
return ;
}
上一篇:模拟javascript中的sort排序


下一篇:hdu2222Keywords Search