〔USACO16OPEN〕 248 G 踩坑QwQ

发表于 更新于
做DP,踩大坑,QwQ 出师不利 QwQ

  🧐题目链接luogu

  坑点:区间合并的合法性

本来想练练板子,套套规律, 刷刷AC率的。没想到踩大坑了QwQ

所有的解释在代码中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int n,ans=0,in[1000];
int f[500][500];
int main() {
  // freopen("in.txt","r",stdin);
  scanf("%d",&n);
  for(int i=1;i<=n;i++){scanf("%d",&in[i]);}
  for(int i=1;i<=n;i++){f[i][i]=in[i];ans=max(ans,in[i]);}
	
  for(int len=2;len<=n;len++){
	for(int l=1,r=len;r<=n;l++,r++){
	  for(int k=l;k<=r;k++){
		if (f[l][k]==f[k+1][r]){
		  f[l][r]=max(f[l][r],f[l][k]+1);
			ans=max(ans,f[l][r]);
		  }
			///////////////////////////////////////////////////////////////////////
			// else f[l][r]=max(f[l][r],max(f[l][k],f[k+1][r]));/////////////////// 
			//hack样例 3     2 1 2   (源于洛谷@lhzawa)///////////////////////////////
			//这个写法就是   不是完全相同也能合并了///////////////////////////////////////
			//你看,在区间1~2的时候，有数1,2那么会执行这一句，f[1][2]答案为2//////////////////
			//但是我们知道,这里不能这样和并,要不后面3好位的合并就会出现错误,///////////////////
			//我们的意思是取两个小区间的最大值作为区间结果的,////////////////////////////////
			//那么我们可以提前预处理,直接找到最大区间的1~n的(如果1~n的都无法正常合并)///////////
			//这算是一个非常隐蔽的错误了////////////////////////////////////////////////
			//////////////////////////////////////////////////////////////////////
	  }
	}
  }
  // cout<<f[1][n]<<"\n";
  cout<<ans<<"\n";//其实只要把endl改为"\n",用printf()和cout都一样
  return 0;
}

PS:vscode有毒,我的斜杠怎么对不齐啊,明明都是英文标点QwQ,我的强迫症啊

[补] luogu [SDOI2008] 石子合并并不是区间DP,QwQ,exlg,这题是Garsia-Wachs算法

[cover 画师 - ヒトこもる]选它原因,我踩坑后的心情 (绝对不是因为她可爱(●'◡'●))

🍂全文完↩︎