bzoj4580:[Usaco2016Open]248（dp）

Description

Input

Output

Sample Input

Sample Output

HINT

Source

题解：dp

f[i][j][k]表示区间[i,j]变成k是否可行，然后每次得到一个新的数就更新答案。理论复杂度不是很科学，但是有很多的不合法状态可以舍去。

其实可以变成二维的转移，f[i][j]表示区间[i,j]合并成一个数的最大值。那么这样会不会有一个值不这么合并的时候更优呢？因为是枚举长度和区间，所以那样一定是某种状态下的最优值，一定会更新进答案。

#include
#include
#include
#include
#include
#define N 300
using namespace std;
int a[N],f[N][N][N],n;
int main()
{
	freopen("248.in","r",stdin);
	freopen("248.out","w",stdout);
	scanf("%d",&n); int ans=0; int minn=40;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),ans=max(ans,a[i]),minn=min(minn,a[i]);
	memset(f,0,sizeof(f));
	for (int i=1;i<=n;i++) f[i][i][a[i]]=1;
	for (int len=2;len<=n;len++)
	 for (int i=1;i<=n;i++) {
	 	int pos=i+len-1;
	 	if (pos>n) break;
	 	int t=ans;
	 	for (int col=minn;col<=t;col++)
	 	{
	 	 for (int k=i;k