【Study】AtCoder DP Contest 做题记录

Educational DP Contest

A - Frog 1

题目

水题，设 \(f[i]\) 为在第 \(i\) 个点的最小花费，容易得出

\(f[i]=min(f[i-1],f[i-2])+cost\)

初始化 \(f[1]=0\) , \(f[2]=abs(a[1]-a[2])\)

B - Frog 2

题目

同上，只是第 \(i\) 个是由 \(i-k\) 到 \(i-1\) 的点转移过来而已，复杂度是 \(O(nk)\) ，无需优化。

注意数组不要越界。

C - Vacation

题目

也是一道线性 \(dp\) 。

设 \(f[i][1/2/3]\) 为取第 \(i\) 个的 \(A/B/C\) 时的最大值，易得：

\(f[i][1]=max(f[i-1][2],f[i-1][3])+a[i][1]\)

\(f[i][2]=max(f[i-1][1],f[i-1][3])+a[i][2]\)

\(f[i][3]=max(f[i-1][1],f[i-1][2])+a[i][3]\)

D - Knapsack 1

题目

01背包问题。

设 \(f[i]\) 为消耗 \(i\) 体积时可获得的最大价值，

\(f[i]=max(f[i],f[i-w[j]]+v[j])\)

01背包，倒序枚举。

E - Knapsack 2

题目

也是一道背包问题，但发现体积非常大，没法根据体积来求最大价值。

仔细读题，发现价值不大，换个思路，也许可以根据价值来求最小体积。

设 \(f[i]\) 为获得 \(i\) 价值时需要耗费的最小体积，则有：

\(f[i]=min(f[i],f[i-v[j]]+w[j])\)

初始化，要将 \(f[i]\) 赋值为 \(INF\) , \(f[0]=0\)

对于答案，我们可以从最大的价值开始枚举，当发现获得该价值时需要的体积小于等于提供的体积，则输出价值。

memset(f,INF,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
	for(int j=MAXN;j>=v[i];j--)
		f[j]=min(f[j],f[j-val[i]]+wei[i]);
for(int i=MAXN;i>=0;i--)
	if(f[i]<=w)
	{
		printf("%d",i);
		break;
	}

（回顾上一道题，其实可以发现题目给的体积比较小，但是价值非常大。）

F - LCS

题目

经典的最长公共子序列，只是这一道题要输出的时公共子序列。

设 \(f[i][j]\) 为 \(A\) 串前 \(i\) 个字符， \(B\) 串前 \(j\) 个字符的最长公共子序列，可以推出：

当 \(A[i]=B[j]\) 时， \(f[i][j]=max(f[i][j],f[i-1][j-1]+1)\)
否则 \(f[i][j]=max(f[i-1][j],f[i][j-1])\)

对于输出，可以设两个指针 \(i\) 和 \(j\) 分别扫 \(A\) 和 \(B\) ，如果 \(A[i]=B[j]\) ，则输出字符，并且 \(i++\) , \(j++\)；如果 \(f[i][j]=f[i+1][j]\) ，说明 \(A[i]\) 不在答案中， \(i++\) ；否则 \(j++\) 。

for(int i=la-1;i>=0;i--)
	for(int j=lb-1;j>=0;j--)
		if(A[i]==B[j])
			f[i][j]=max(f[i][j],f[i+1][j+1]+1);
		else f[i][j]=max(f[i+1][j],f[i][j+1]);
int i=0,j=0;
while(i<la&&j<lb)
{
	if(A[i]==B[j])
	{
		cout<<A[i];
		i++;j++;
	}
	else if(f[i][j]==f[i+1][j]) i++;
	else j++;
}

G - Longest Path

题目

求最长的路径。

分析样例，发现最长的路径一定是从入度为 \(0\) 的点开始出发的，将这些点压入队列进行 \(BFS\) 。从队列里的点跑向其他点的时候将其他点的入度减 \(1\) ，则剩下的图又变成了一个最长路径问题，继续将新的入度为 \(0\) 的点压入队列。

设 \(f[v]\) 为到达第 \(i\) 个点时的最长路径，则

\(f[v]=max(f[v],f[u]+1)\) ，其中点 \(u\) 有一条到点 \(v\) 的边。

for(int i=1;i<=n;i++)
	if(!ei[i])	
		q.push(i);
while(!q.empty())
{
	int u=q.front();q.pop();
	for(int i=Head[u];i;i=a[i].nex)
	{
		int v=a[i].t;
		f[v] = max(f[u]+1,f[v]);
		ans=max(ans,f[v]);
		ei[v]--;
		if(!ei[v]) q.push(v);
	}
}
printf("%d",ans);

H - Grid 1

题目

可以直接暴力递推，复杂度是 \(O(HW)\) 的。

设 \(f[i][j]\) 为到达格 \((i,j)\) 时的方案数，则有

如果格 \((i-1,j)\) 不是障碍， \(f[i][j]+=f[i-1][j]\)
如果格 \((i,j-1)\) 不是障碍， \(f[i][j]+=f[i][j-1]\)

初始化 \(f[i][j]=1\) ，答案为 \(f[H][W]\)

I - Coins

题目

基础的概率 \(dp\)

设 \(f[i][j]\) 为前 \(i\) 个硬币有 \(j\) 个硬币为正面时的概率，可以推出：

第 \(i\) 个硬币为正 \(f[i][j]+=f[i-1][j-1]*p[i]\)
第 \(i\) 个硬币为反 \(f[i][j]+=f[i-1][j]*(1-p[j])\)

特别的， \(f[i][0]=f[i-1][0]*(1-p[i])\) ， \(f[0][0]=1\)

f[0][0]=1;
for(int i=1;i<=n;i++)
{
	f[i][0]=f[i-1][0]*(1-p[i]);
	for(int j=1;j<=i;j++)
		f[i][j]=f[i-1][j]*(1-p[i])+f[i-1][j-1]*p[i];
}
for(int i=(n+1)/2;i<=n;i++)
	ans+=f[n][i];

J - Sushi

题目

期望 \(dp\) 。

\(N\) 比较大，反正不能开一个 \(N\) 维的数组来记录。

注意到每个盘子的寿司不大于 \(3\) ，因为每个盘子被选到的概率是相同的，所以我们只需要关心寿司数量为 \(1\) , \(2\) , \(3\) 的盘子有多少个。

设 \(f[i][j][k]\) 为 \(i\) 个盘子上有 \(1\) 个寿司， \(j\) 格盘子上有 \(2\) 个寿司， \(k\) 个盘子上有 \(3\) 个寿司，则

\(f[i][j][k]=f[i-1][j][k]*(a/(a+b+c))+f[i+1][j-1][k]*(b/(a+b+c))+f[i+1][j][k-1]*(c/(a+b+c))+n/(a+b+c)\)

这个东西用记忆化搜索来写比较方便。

double Dfs(int x,int y,int z)
{
	double &tmp=f[x][y][z];
	if(x==0&&y==0&&z==0) return 0;
	if(tmp) return tmp;
	tmp=1.0*n/(x+y+z);
	if(x)tmp+=Dfs(x-1,y,z)*x/(x+y+z);
	if(y)tmp+=Dfs(x+1,y-1,z)*y/(x+y+z);
	if(z)tmp+=Dfs(x,y+1,z-1)*z/(x+y+z);
	return tmp;
}

K - Stones

题目

一道博弈论，设 \(f[i][0/1]\) 表示当取剩 \(i\) 个石头的时候，甲乙分别是赢或输，当值为 \(1\) 的时候表示赢。那么可以得出：

\(f[i][now]|=!f[i-a[1...n]][!now]\)

（当 \(f[i-a[j]][0]\) 为 \(0\) ，此时 \(1\) 号取 \(a[j]\) 个必赢，所以 \(f[i][1]\) 为 \(1\)）

可以用记忆化搜索实现

int Dfs(int k,int now)
{
	if(f[k][now]) return f[k][now];
	if(!k) return 0;
	for(int i=1;i<=n;i++)
		if(k>=a[i]) f[k][now]|=(Dfs(k-a[i],now^1)^1);
	return f[k][now];
}

L - Deque

题目

区间 \(dp\) 好题。

设 \(f[i][j]\) 为选手在区间 \([i,j]\) 中可以取到的最大值。

考虑转移，当甲取最左边的值时，轮到乙取剩下的区间 \([l+1,r]\) ，可以取到的最大值为 \(f[l+1][r]\) , 则甲可以在 \([l+1,r]\) 中取到的最大值就为 \(sum[l+1,r]-f[l+1][r]\) ，其中 \(sum[l+1][r]\) 表示区间 \([l+1][r]\) 的和。

则 \(f[l][r]=a[l]+sum[l+1][r]-f[l+1][r]\)

对于取最右边的值同理。

同样用记忆化搜索比较方便。

int Dfs(int l,int r)
{
	if(f[l][r]) return f[l][r];
	if(l==r) return f[l][r]=a[l];
	return f[l][r]=max(a[l]+(s[r]-s[l])-Dfs(l+1,r),a[r]+(s[r-1]-s[l-1])-Dfs(l,r-1));
}

M - Candies

题目

是一道好背包。

设 \(f[i][j]\) 为前 \(i\) 个小孩已经取了 \(j\) 个糖果的方案数，容易写出：

\(f[i][j]=\sum\limits_{k=0}^{a[i]}f[i-1][j-k]\)

初始化 \(f[0][0]=1\)

但是这样时间复杂度是 \(O(nk^2)\) ，想办法优化一个 \(k\)

可以发现，\(f[i][j]\) 是从 \(f[i-1][k]\) 转移过来的，其中 \(a[i]-j≤k≤j\) ，而对于 \(f[i][j-1]\) 是从 \(f[i-1][k']\) 转移过来的，其中 \(a[i]-j-1≤k'≤j-1\) ，那我们可以其实可以用一个 \(sum\) 来维护这个区间的值，对于下一次枚举的时候只要删掉超出区间的一个，加入新进入区间的一个就行了。

（其实这样有点类似单调队列）

for(int i=1;i<=n;i++)
{
	int sum=0;
	for(int j=0;j<=k;j++)
	{
		sum+=f[i-1][j];
		if(j>a[i]) sum-=f[i-1][j-a[i]-1];
		f[i][j]=(sum+mod)%mod;
	}
}

N - Slimes

题目

石子合并问题。

设 \(f[i][j]\) 为合并区间 \([i,j]\) 需要的最小花费，则：

\(f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[i][j])\)

其中 \(i≤k<j\) ， \(sum[i][j]\) 表示区间 \([i,j]\) 的和

memset(f,INF,sizeof(f));
for(int i=1;i<=n;i++) f[i][i]=0,s[i]=s[i-1]+a[i];
for(int len=2;len<=n;len++)
	for(int l=1;l+len-1<=n;l++)
	{
		int r=l+len-1;
		for(int k=l;k<r;k++)
			f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
	}
printf("%lld",f[1][n]);

O - Matching

题目

求二分图的最大匹配数的方案数。

发现 \(N\) 非常小，应该是一道状压 \(dp\) 。

设 \(f[i][s]\) 为匹配了 \(i\) 个男生，且匹配女生的状态为 \(s\) , 不难写出：

\(f[i][s]= \sum\limits_{s}^{s \ and\ (1<<(i-1)) ==1}f[i-1][s\ xor\ (1<<(i-1))]\)

其中 \(s\) 中 \(1\) 的个数要与 \(i\) 对应

初始化 \(f[0][0]=1\)

for(int i=1;i<(1<<n);i++)
{
	int qwq=0,aaa=i;
	while(aaa)
	{
		if(aaa&1) qwq++;
		aaa>>=1;
	}
	v[qwq].push_back(i);
}
f[0][0]=1;
for(int i=1;i<=n;i++)
	for(int j=0;j<v[i].size();j++)
	{
		int s=v[i][j];
		for(int k=1;k<=n;k++)
		{
			if(!a[i][k]) continue;
			if(!(s&(1<<(k-1)))) continue;
			f[i][s]+=f[i-1][s^(1<<(k-1))];
			f[i][s]%=mod;
		}
	}
printf("%lld",f[n][(1<<n)-1]);

P - Independent Set

题目

简单的树形 \(dp\)

设 \(f[i][1/0]\) 为节点 \(i\) 染为黑/白色的方案数，可得：

若 \(u\) 点为白， \(f[u][0]=\prod\limits_{v}^{E[u][v]}(f[v][0]+f[v][1])\)
若 \(u\) 点为黑， \(f[u][1]=\prod\limits_{v}^{E[u][v]}f[v][1]\)

其中 \(E[u][v]\) 表示 \(u\) , \(v\) 之间有连边。

初始化 \(f[u][0]=f[u][1]=1\)

void Dfs(int u,int fa)
{
	f[u][1]=f[u][0]=1;
	for(int i=Head[u];i;i=a[i].nex)
	{
		int v=a[i].t;
		if(v==fa) continue;
		Dfs(v,u);
		f[u][0]*=((f[v][0]+f[v][1])%mod);f[u][0]%=mod;
		f[u][1]*=f[v][0];f[u][1]%=mod;
	}
}
void Work()
{
	Dfs(1,0);
	printf("%lld",(f[1][0]+f[1][1])%mod);
}

Q - Flowers

题目

是一道变形的 \(LIS\) ，设 \(f[i]\) 为前 \(i\) 的最大价值，则有

\(f[i]=max(f[i],max(f[j]*(h[i]≥h[j])))\)

其中 \(1≤j≤i-1\)

这样做的时间复杂度是 \(O(N^2)\) ，会超时，考虑优化。

对于第 \(i\) 朵花，实际转移过来的只有那些 \(h[j]≤h[i]\) 的花朵，所以我们需要维护 \([1,h[i]-1]\) 的区间最值，可以用线段树进行维护。

struct Node{
	int l,r,m;
}t[MAXN<<2];
void Pushup(int x)
{
	t[x].m=max(t[x<<1].m,t[x<<1|1].m);
}
#define mid ((l+r)>>1)
void Build(int x,int l,int r)
{
	t[x].l=l;t[x].r=r;
	if(l==r) return ;
	Build(x<<1,l,mid);
	Build(x<<1|1,mid+1,r);
	Pushup(x);
}
#undef mid
void Updata(int x,int i,int v)
{
	if(t[x].l>i||t[x].r<i) return ;
	if(t[x].l==t[x].r){t[x].m=v;return ;}
	Updata(x<<1,i,v);
	Updata(x<<1|1,i,v);
	Pushup(x);
}
int Query(int x,int l,int r)
{
	if(t[x].l>r||t[x].r<l) return 0;
	if(l<=t[x].l&&t[x].r<=r) return t[x].m;
	return max(Query(x<<1,l,r),Query(x<<1|1,l,r));
}
void Work()
{
	Build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		int qwq=Query(1,1,a[i]-1);
		Updata(1,a[i],b[i]+qwq);
	}
	printf("%lld",t[1].m);
}

R - Walk

题目

读题，发现 \(k\) 特别的大，考虑用矩阵快速幂。

设 \(f[i][j]\) 为点 \(i\) 到点 \(j\) 的用了 \(k\) 步方案数。

对于原图 \(a[i][j]\) ，如果 \(a[i][j]=1\) ，则此时 \(f[i][j]\) 就要乘上 \(f[j][1...n]\) ，这个东西就是矩阵乘法。我们不需要再在 \(f\) 上多个 \(k\) 维，将 \(f\) 与自身相乘的时候每个点的值所代表的步数都是同时增加的，我们只需要将 \(f\) 与自身乘 \(k\) 次就可以得到答案。又因为这里的 \(k\) 很大，需要用到快速幂。

其实和这道题是一模一样的 P2886 [USACO07NOV]Cow Relays G

struct M{
	long long a[51][51];
	M(){memset(a,0,sizeof(a));}
};
int n;
M Mul(M a,M b)
{
	M awa;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				awa.a[i][j]+=(a.a[i][k]*b.a[k][j]%mod),awa.a[i][j]%=mod;
	return awa;
}
M Power(M a,long long k)
{
	M ans;
	for(int i=1;i<=n;i++)
		ans.a[i][i]=1;
	while(k)
	{
		if(k&1) ans=Mul(ans,a);
		a=Mul(a,a);
		k>>=1;
	}
	return ans;
}
M qwq;
long long k,ans;
void Work()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			qwq.a[i][j]=Read();
	qwq=Power(qwq,k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ans+=qwq.a[i][j],ans%=mod;
	printf("%lld",ans);
}

S - Digit Sum

题目

一道基础的数位 \(dp\) 。

利用字符串输入 \(K\) ，在将每一位的数提取出来进行数位 \(dp\) 。

int num[MAXN],n,f[MAXN][2][105];
int Dfs(int pos,int lim,int qwq)
{
	int &tmp=f[pos][lim][qwq];
	if(~tmp) return tmp;
	if(!pos) return tmp=(qwq==0);
	tmp=0;
	int bg=0,fn=lim?num[pos]:9;
	for(int i=bg;i<=fn;i++)
		tmp+=Dfs(pos-1,i==fn&&lim,(qwq+i)%n),tmp%=mod;
	return tmp%mod;
}
int Solve(char *c)
{
	memset(f,-1,sizeof(f));
	int lc=strlen(c),pos=lc;
	for(int i=lc;i>=1;i--) num[i]=c[lc-i]-48;
	return Dfs(pos,1,0)-1;
}

对于记忆化搜索后得出的答案需要减去 \(1\) ，因为对于 \(000...0\) 这个东西会对答案有贡献，需要减去。

T - Permutation

题目

神仙区间 \(dp\) 。

设 \(f[i][j]\) 为前 \(i\) 个数的排列中最后一个数为 \(j\) 的方案数，则有：

如果是 \(>\) ，则 \(f[i][j]=\sum\limits^{i}_{k=j+1}f[i-1][k]\)
如果是 \(<\) ，则 \(f[i][j]=\sum\limits^{j}_{k=1}f[i-1][k]\)

对于 \(>\) 比较好理解，对于 \(<\) ，为什么可以枚举到 \(j\) 呢，假设有一数列
\((1,3,2)\) ，我们推 \(f[4][3]\) ，此时在该数列最后加上 \(3\) ，但是又重复了一个 \(3\) ，我们可以将原数列中大于等于 \(3\) 的数都给其加上 \(1\) ，在最后插入 \(3\) ，此时为 \((1,4,2,3)\) ，这样子就不会重复，并且这样的数列是满足原来的限制条件的。

对于上面的转移方程，其时间复杂度是 \(O(n^3)\) ，需要采取优化。

我们可以发现求 \(f[i-1][]\) 那一部分的时候是可以用前缀和优化的。假如对于\(f[i][j]=\sum\limits^{i}_{k=j+1}f[i-1][k]\) ，可以发现 \(f[i][j]\) 的一部分答案已经储存在 \(f[i][j-1]\) 中，此时就可以 \(f[i][j]=f[i][j-1]+f[i-1][j-1]\) 。对于另一条转移方程式也是同理的。

f[1][1]=1;
for(int i=2;i<=n;i++)
{
	f[i][1]=0;
	if(s[i-2]=='>')
		for(int j=2;j<=i;j++)
			f[i][j]=(f[i-1][j-1]+f[i][j-1])%mod;
	else
		for(int j=i-1;j>=1;j--)
			f[i][j]=(f[i-1][j]+f[i][j+1])%mod;
}	
for(int i=1;i<=n;i++) ans+=f[n][i],ans%=mod;
printf("%d",ans);

U - Grouping

题目

\(N\) 很小，应该是一道状压 \(dp\) 。

设 \(f[s]\) 为已选取成员的状态为 \(s\) 时可以获得的最大值，则可以推出：

\(f[s]=max(f[s_1],f[s_2])\)

其中 \(s_1\) ， \(s_2\) 均为 \(s\) 的子集，并且 \(s_1\ xor\ s_2=s\)

现在的问题就是要如何枚举子集。

for(int s1=s;s1;s1=(s1-1)&s)
{
	int s2=s^s1;
	...
}

这样就可以不重不漏枚举 \(s\) 中的每一个子集，并且可以保证 \(s_1\) 和 \(s_2\) 中不会有同个位置的 \(1\) ，时间复杂度是 \(O(3^n)\) 。

注意对于这一道题，要枚举的是真子集。

for(int s=1;s<(1<<n);s++)
{
	for(int i=1;i<=n;i++)
	{
		if(!(s&(1<<(i-1)))) continue;
		for(int j=1;j<=i;j++)
		{
			if(!(s&(1<<(j-1)))) continue;
			f[s]+=a[i][j];
		}
	}
	for(int qwq=((s-1)&s);qwq;qwq=((qwq-1)&s))
		f[s]=max(f[s],f[qwq]+f[s^qwq]);
}
printf("%lld",f[(1<<n)-1]);

V - Subtree

题目

毒瘤的树形 \(dp\) ，需要二次扫描和换根。

设 \(g[u]\) 表示从根节点（固定点）出发，将 \(u\) 号节点染黑，满足条件的方案数。对于 \(u\) 的根节点为 \(v\) 子树， \(v\) 节点有染和不染两种情况，那么可以推出：

\(g[u]=\prod\limits_{v}^{E[u][v]}(g[v]+1)\)

其中 \(E[u][v]\) 表示 \(u\) , \(v\) 之中有连边。

初始化 \(g[u]=1\)

对于根节点是这样子，那么对于其他的节点就需要考虑换根。

设 \(f[u]\) 表示以 \(u\) 为根节点是的方案数。

显然有 \(f[root]=g[root]\)

假设当前新的根节点为 \(u\) ，那么此时 \(u\) 就不会对 \(fa_u\) 有答案贡献，那么

\(f[fa_u]=\dfrac{g[fa_u]}{g[u]+1}\)

并且 \(f[u]\) 之中还应该要有 \(f[fa_u]\) 的贡献，

\(f[u]=f[u]*(f[fa_u]+1)\)

这样就基本完成了。

但是难受的是，这里面有除法，有取模，要写逆元，但模数不是质数，这里就不能用逆元处理。

我们可以在求 \(g[u]\) 的时候处理出 \(\prod\limits_{v}^{E[u][v]}(g[v]+1)\) 的前缀积和后缀积，在求 \(f[u]\) 的时候就不需要除法，只需以要除掉的东西为分界，乘上其左边的前缀积与其右边的后缀积便好。

vector<int> a[MAXN],qwq[MAXN];
vector<int> pre[MAXN],suf[MAXN];
void Dfs(int u,int fa)
{
	g[u]=1;
	for(int i=0;i<a[u].size();i++)
	{
		int v=a[u][i];
		if(v==fa) continue;
		qwq[u].push_back(v);
		Dfs(v,u);
		g[u]*=(g[v]+1);g[u]%=m;
	}
	pre[u].push_back(1);
	for(int i=0;i<qwq[u].size();i++)
		pre[u].push_back(pre[u][i]*(g[qwq[u][i]]+1)%m);
	suf[u].push_back(1);
	for(int i=qwq[u].size()-1,j=0;i>=0;i--,j++)
		suf[u].push_back(suf[u][j]*(g[qwq[u][i]]+1)%m);
	reverse(suf[u].begin(),suf[u].end());
}
void Solve(int u,int gfa)
{
	f[u]=g[u]*(gfa+1)%m;
	for(int i=0;i<qwq[u].size();i++)
		Solve(qwq[u][i],pre[u][i]*suf[u][i+1]%m*(gfa+1)%m);
}
void Work()
{
	Dfs(1,0);
	Solve(1,0);
	for(int i=1;i<=n;i++)
		printf("%lld\n",f[i]);

}

W - Intervals

题目

难题qwq。

一般来说，对于这种题的套路，都是要先排序的，我们可以以 \(r\) 为非降序进行排序。

设 \(f[i]\) 为目前在第 \(i\) 个位置，且第 \(i\) 个位置填 \(1\) 的最大价值，可以推出：

\(f[i]=f[j]+a[k]\)

其中 \(j<l[k]≤i≤r[k]\)

这么打会超时，考虑优化。

其实对于上面的转移本质上就是一次对区间 \([\ l[k],r[k]\ ]\) 内的 \(f\) 进行转移，再一起修改，对于区间的修改我们可以想到线段树。

当 \(i\) 不是某个区间的右端点时，我们先需要将其赋值为 \(max(f[j])\) ，其中 \(1≤j≤i-1\) 。虽然需要 \(j<l[k]\) ，但是我们目前区间仍未修改，则 \(max(f[j])=f[l[k]]=f[l[k]+1]=...=f[i]\) ，不会对前面的最大值造成影响。

当 \(i\) 为某个区间的右端点时，此时 \(f[\ l[k],r[k]\ ]\) 已经赋值为 \(max(f[1],f[2],...,f[\ l[k]-1\ ])\) ，可以对区间进行修改完成方程转移。

所以这也是我们首先要将区间按 \(r\) 非降序进行排列。

bool cmp(const qwq&a,const qwq&b){return a.r<b.r;}
struct Node{
	int l,r,v,laz;
	Node(){laz=0;v=-INF;}
}t[MAXN<<2];
void Pushup(int x){t[x].v=max(t[x<<1].v,t[x<<1|1].v);}
void Pushdown(int x)
{
	if(t[x].laz)
	{
		t[x<<1].laz+=t[x].laz;
		t[x<<1].v+=t[x].laz;
		t[x<<1|1].laz+=t[x].laz;
		t[x<<1|1].v+=t[x].laz;
		t[x].laz=0;
	}
}
#define mid ((l+r)>>1)
void Build(int x,int l,int r)
{	
	t[x].l=l;t[x].r=r;
	if(l==r) return ;
	Build(x<<1,l,mid);Build(x<<1|1,mid+1,r);
}
#undef mid
void Updata(int x,int l,int r,int v,int aaa)
{
	if(t[x].l>r||t[x].r<l) return ;
	if(l<=t[x].l&&t[x].r<=r)
	{
		if(aaa)
			t[x].v+=v,t[x].laz+=v;
		else
			t[x].v=v;
		return ;
	}
	Pushdown(x);
	Updata(x<<1,l,r,v,aaa);Updata(x<<1|1,l,r,v,aaa);
	Pushup(x);
}
int Query(int x,int l,int r)
{
	if(t[x].l>r||t[x].r<l) return 0;
	if(l<=t[x].l&&t[x].r<=r) return t[x].v;
	Pushdown(x);
	return max(Query(x<<1,l,r),Query(x<<1|1,l,r)); 
}
void Work()
{
	sort(a+1,a+m+1,cmp);
	Build(1,1,n);
	int awa=1;
	for(int i=1;i<=n;i++)
	{
		Updata(1,i,i,Query(1,1,i-1),0);
		while(a[awa].r==i) Updata(1,a[awa].l,a[awa].r,a[awa].v,1),awa++;
	}
	printf("%lld",max(0ll,t[1].v));
}

X - Tower

题目

能感觉是一道背包问题。

设 \(f[i]\) 表示重量为 \(i\) 最大价值，为了保证当前重量满足物体承载重量，可以写出：

\(f[i+w[j]]=max(f[i+w[i]],f[i]+v[j])\)

其中 \(0≤i≤s[j]\)

然后发现发现过不了样例，感觉应该先对物品进行排序。

设两物品 \(x\) 和 \(y\) ，前面的物体重量为 \(W\) ，当 \(x\) 放在 \(y\) 上时 \(y\) 还能承受的重量为 \(s_y-w_x-W\) ，反之， \(x\) 还能承受的重量为 \(s_x-w_y-W\) ，我们需要使物体还能承受的质量尽量大，不妨设 \(s_x-w_y-W>s_y-w_x-W\) ，即我们希望物体 \(x\) 能放在物体 \(y\) 的下方，物体 \(x\) 能尽量晚点来转移到，化简上面不等式，可得 \(s_y+w_y<s_x+w_x\) ，所以我们就需要先依照该条件对物品进行排序，再进行背包。

bool cmp(const Node&a,const Node&b){return a.w+a.s<b.w+b.s;}
void Work()
{
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
		for(int j=a[i].s;j>=0;j--)
			f[j+a[i].w]=max(f[j+a[i].w],f[j]+a[i].v);
	int ans=0;
	for(int i=0;i<=a[n].s+a[n].w+1;i++) 
		ans=max(f[i],ans);
}

Y - Grid 2

题目

好题。

读题发现 \(H\) ，\(W\) 都很大，不能直接像前面那道题目一样直接 \(dp\) 求方案数。考虑用数学做法。

由组合数学的知识可以得出，当两格之间无障碍时，格 \((1,1)\) 到格 \((h,w)\) 的路径总数一共有 \(\binom{h-1+w-1}{h-1}\) 或 \(\binom{h-1+w-1}{w-1}\) 条。

再运用容斥的思想，若两个格之间有一个障碍的时候，起点到终点的路径总数就应该等于 \(\binom{h_2+w_2-h_1-w_1}{h_2-h_1}\) 减去起点到障碍的方案数乘障碍到终点的方案数。

我们可以将 \((H,W)\) 看做一个障碍，将障碍离起点排列一下，设 \(f[i]\) 为 \((1,1)\) 到达第 \(i\) 个障碍时的方案数，则可以得到：

\(f[i]=\binom{x_i-1+y_i-1}{x_i-1}-\sum\limits_{j=1}^{i-1} f[j]*\binom{x_i+y_i-x_j+y_j}{x_i-x_j}\)

这里面有除法，记得要求逆元。

struct qwq{
	int x,y;
}a[MAXN];
bool cmp(const qwq&a,const qwq&b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}
int Power(int a,int k)
{
	int ans=1;
	while(k)
	{
		if(k&1) ans*=a,ans%=mod;
		a*=a,a%=mod;
		k>>=1;
	}
	return ans%mod;
}
int fac[MAXN];
void Init()
{
	fac[0]=fac[1]=1;
	for(int i=2;i<=MAXN-100;i++) fac[i]=fac[i-1]*i,fac[i]%=mod;
}
int C(int a,int b)
{
	return fac[a]*Power(fac[a-b],mod-2)%mod*Power(fac[b],mod-2)%mod;
}
int f[MAXN],n,h,w;
void Work()
{
	Init();
	a[++n].x=h;a[n].y=w;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		f[i]=C(a[i].x+a[i].y-2,a[i].x-1);
		for(int j=1;j<i;j++)
			f[i]-=f[j]*C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x)%mod,f[i]+=mod,f[i]%=mod;
	}
}

Z - Frog 3

题目

设 \(f[i]\) 为跳到第 \(i\) 个石头上的最小花费，可得：

\(f[i]=\min\limits_{j<i}(f[j]+(h[i]-h[j])^2+C)\)

时间复杂度是 \(O(n^2)\) ,需要优化。

显然这个式子可以斜率优化。

int h[MAXN],f[MAXN],n,c;
double X(int i){return h[i];}
double Y(int i){return f[i]+h[i]*h[i];}
double K(int i,int j){return (Y(j)-Y(i))/(X(j)-X(i));}
int q[MAXN],Head,Tail=1;
void Work()
{
	n=Read();c=Read();
	for(int i=1;i<=n;i++) h[i]=Read();
	f[1]=0;q[++Head]=1;
	for(int i=2;i<=n;i++)
	{
		while(Head<Tail&&h[i]*2>=K(q[Head],q[Head+1])) Head++;
		f[i]=f[q[Head]]+(h[q[Head]]-h[i])*(h[q[Head]]-h[i])+c;
		while(Head<Tail&&K(i,q[Tail])<=K(q[Tail],q[Tail-1])) Tail--;
		q[++Tail]=i;
	}
	printf("%lld",f[n]);
}