IOI2021集训队作业 CK String Theory

一个带引号的字符串，引号有多级，第(i)级引号用(i)个'来表示。

现在给你一个字符串：(a_i)表示有(a_i)个'连在一起，(a_i)和(a_{i+1})间有分隔。

合法的(k)级引号串为：最外层为(k)-引号，其中包含的串要么为普通串，要么为(k-1)-引号串。(k>1)时内部不能为空。

(nle 100,a_ile 100)

---

可以发现：可以如此构造这样的最优方案，当(k>2)时，(k)引号串内部的(k-1)引号至多有一对。

解释：任何方案都可以转化：将(k)引号串内部的(k-1)引号保留最左边和最右边，多余的全部转化成(1)引号。对于所有(k)如此操作，发现一定是合法的。

于是简单DP：设(f_{s,k})表示左边和右边各用了(s)个，最内层为(k)引号，此时最外层引号最多是多少。

---

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 105
int n,a[N];
int f[N*N][N];
void upd(int &a,int b){a=max(a,b);}
int main(){
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	int sum=0;
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]),sum+=a[i];
	if (sum&1){
		printf("no quotation
");
		return 0;
	}
	if (sum==2){
		printf("1
");
		return 0;
	}
	int m=min(a[1],a[n]),ans=0;
	for (int k=m;k>=2;--k)
		f[k][k]=k;
	for (int s=0,i=1,j=n;s<sum;++s){
		for (int k=m;k>=1;--k)
			if (f[s][k]){
				if (i!=j){
					if (k-1<=a[i] && k-1<=a[j])
						upd(f[s+k-1][k-1],f[s][k]);
				}
				else{
					if ((k-1)*2<=a[i])
						upd(f[s+k-1][k-1],f[s][k]);
				}
			}
		if (!--a[i]) ++i;
		if (!--a[j]) --j;
	}
	for (int i=1;i<=sum/2;++i)
		upd(ans,f[i][1]);
	if (ans==0)
		printf("no quotation
");
	else
		printf("%d
",ans);
	return 0;
}