P3147 [USACO16OPEN]262144
一道非常有趣的游戏，不，题目。
当数据水时，可以这样表示状态。
f[i][j]表示合并[i,j]区间所能得到的最大值，有点floyed的小味道。
if(f[i][k]==f[k+1][j])
f[i][j]=max(f[i][k]+1,f[i][j]);
不断更新答案。
这样需要枚举左右端点和中间点，O(n^3)
300以内的数据可以水过。
状态的设定直接把dp拉到暴力里去了。
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.10.26
using namespace std;
int n;
int x;
int f[][];
int ans;
void in(int &x)
{
int y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=x*+c-'',c=g();
x*=y;
}
void o(int x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
}
int main()
{
in(n);
For(i,,n)
{
in(x);
f[i][i]=x;
}
For(j,,n)
for(int i=j;i>=;i--)
For(k,i,j-)
if(f[i][k]==f[k+][j])
{
f[i][j]=max(f[i][k]+,f[i][j]);
ans=max(ans,f[i][j]);
}
o(ans);
return ;
}
O.O
优化状态：
有点倍增的小味道。
i表示数值，j表示区间的左端点，f[i][j]表示右端点，如果存在这样的右端点，就把ans更新为i。怎么转移呢？
if(!f[i][j]&&f[i-1][j])
f[i][j]=f[i-1][f[i-1][j]+1];
画个图就明白了。
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.10.26
using namespace std;
int n;
int x;
int f[][];//18M
int ans;
void in(int &x)
{
int y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=x*+c-'',c=g();
x*=y;
}
void o(int x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
}
int main()
{
in(n);
For(i,,n)
{
in(x);
f[x][i]=i;
}
For(i,,)
For(j,,n)
if(!f[i][j]&&f[i-][j]&&f[i-][f[i-][j]+])
{
f[i][j]=f[i-][f[i-][j]+];
ans=i;
}
o(ans);
return ;
}