LTb的博客

qwqwqwq

【专项训练计划】简单dp

发布于 2020-11-13 | 分类于 专项训练计划 、 アルセチ力 | 22分钟 | 3825字数

简单dp指的是不需要较高难度算法的dp
选取 Codeforces 难度 2100-2500 的 dp 题 进行训练
虽然很多题实际都不怎么像 dp 但是总之做一做没啥坏处（雾
简洁起见把快读去掉了（）

1428F Fruit Sequences

link（*2400）
考虑常规的枚举右端点统计答案的思路
我们称一个极长的全 1 子串为一个连通块
维护一个 dpdp 数组，dpxdp_x 表示最后一个 ii，距离 ii 所在连通块的最后一个位置 jj 长度为 xx（即 j−i=xj-i=x）

每次统计答案的时候分类：如果当前枚举的右端点（称为 ii）ai=0a_i=0 则没有什么贡献，更新一下 dpdp
如果 ai=1a_i=1 则要加上以 ii 为右端点的整个连通块产生的贡献
若上一句提到的这个连通块的长度为 kk，则产生的贡献为 i−dpki-dp_k。
复杂度 O(n)\mathcal{O(n)}

// 2020.11.13
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN=500005;
int n;
bool a[MAXN];
int dp[MAXN];
int ans=0;

signed main()

{
	n=read();
	for (int i=1;i<=n;i++)
		a[i]=readch()=='1';

	int len=0,tmp=0;
	for (int i=1;i<=n;i++){	
		if (a[i]) tmp+=i-dp[++len];
		else{
			while (len) dp[len]=i-len,len--;
		}
		ans+=tmp;
	}

	cout<<ans<<endl;
	return 0;
}

771D Bear and Company

link（*2500）
看到ycx的题解就去做了一下（
设 dpi,j,k,xdp_{i,j,k,x} 为当前移了 ii 个 V，jj 个 P，kk 个其他字母到前 pp（设 p=i+j+kp=i+j+k）个位置的最小操作次数，xx 记录最后一位是否为 V。
随便转移一下就好了
复杂度 O(n4)\mathcal{O(n^4)}

// 2020.11.12
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int MAXN=100;
int n;
vector<int> V={0},K={0},X={0};
int dp[MAXN][MAXN][MAXN][3];

inline int calc(int x,int y,int z,int pos){
	int ans=pos-(x+y+z+1);
	for (int i=1;i<=x;i++) if (V[i]>=pos) ans++;
	for (int i=1;i<=y;i++) if (K[i]>=pos) ans++;
	for (int i=1;i<=z;i++) if (X[i]>=pos) ans++;

	// cout<<x<<' '<<y<<' '<<z<<' '<<pos<<' '<<ans<<endl;
	return ans;
}

signed main()

{
	memset(dp,0x3f3f3f3f,sizeof(dp));
	n=read();
	for (int i=1;i<=n;i++){
		char tmp=readch();
		if (tmp=='V') V.push_back(i);
		else if (tmp=='K') K.push_back(i);
		else X.push_back(i);
	}

	dp[0][0][0][0]=dp[0][0][0][1]=0;

	for (int i=0;i<V.size();i++){
		for (int j=0;j<K.size();j++){
			for (int k=0;k<X.size();k++){
				if (i!=0) dp[i][j][k][1]=min(dp[i][j][k][1],min(dp[i-1][j][k][0],dp[i-1][j][k][1])+calc(i-1,j,k,V[i]));
				if (k!=0) dp[i][j][k][0]=min(dp[i][j][k][0],min(dp[i][j][k-1][0],dp[i][j][k-1][1])+calc(i,j,k-1,X[k]));
				if (j!=0) dp[i][j][k][0]=min(dp[i][j][k][0],dp[i][j-1][k][0]+calc(i,j-1,k,K[j]));
			}
		}
	}

	cout<<min(dp[V.size()-1][K.size()-1][X.size()-1][0],dp[V.size()-1][K.size()-1][X.size()-1][1])<<endl;
	return 0;
}

1420E Battle Lemmings

link（*2500）
设 dpi,j,kdp_{i,j,k} 为考虑到第 ii 个位置且第 ii 个位置为 11，已经进行了 jj 次操作，前 ii 个数中有 kk 个为 1 的最大答案
每次转移枚举下一个填 1 的位置进行更新
时间复杂度 O(n5)\mathcal O(n^5)，看起来完全不可能过但是实际跑得飞快
细节很多，调了一年

// 2020.11.14
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int MAXN=85;
int n;
bool a[MAXN];
vector<int> v;
int dp[MAXN][MAXN*MAXN/2][MAXN];
// dp[i][j][k] 表示前i个，j次操作，k个1
int mx[MAXN][MAXN];

inline int calc(int i,int j,int k,int l){
	return (i-k)*(l-i-1);
}

signed main()

{
	memset(dp,-1,sizeof(dp));
	n=read();
	int N=n*(n-1)/2;
	for (int i=1;i<=n;i++){
		a[i]=read();
		if (a[i]) v.push_back(i);
	}

	dp[0][0][0]=0;
	for (int i=0;i<n;i++){
		for (int j=0;j<N;j++){
			for (int k=min(i,1);k<=min(i,int(v.size()-1));k++){
				// if (j!=0) dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
				if (dp[i][j][k]==-1) continue;
				for (int qwq=i+1;qwq<=n;qwq++){
					int dis=abs(v[k]-qwq);
					if (j+dis>N) continue;
					dp[qwq][j+dis][k+1]=max(dp[qwq][j+dis][k+1],dp[i][j][k]+calc(i,j,k,qwq));
					// printf("dp[%d][%d][%d]=%d\t -> \t dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k] ,qwq,j+dis,k+1,dp[qwq][j+dis][k+1]);
				}
			}
		}
	}

	int ans=0;
	for (int j=0;j<=N;j++){
		int k=v.size();
		for (int i=k;i<=n;i++){
			if (dp[i][j][k]!=-1) ans=max(ans,dp[i][j][k]+max(0,(n-i)*(i-k)));
		}

		cout<<ans<<' ';
	}
	cout<<endl;
	return 0;
}

1409F Subsequences of Length Two

link（*2100）
记 t0t_0 为 a\texttt{a}，t1t_1 为 b\texttt{b}
设 dpi,j,xdp_{i,j,x} 为考虑到第 ii 个位置，用了 jj 次操作， 前面有 xx 个 a\texttt{a} 的答案
随便转移
需要特判一下 a=b\texttt{a}=\texttt{b} 的情况
时间复杂度 O(n3)\mathcal{O(n^3)}

// 2020.11.14
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int MAXN=205;
int n,k;
int a[MAXN];
int dp[MAXN][MAXN][MAXN];
int ans=0;

signed main()

{
	n=read();k=read();
	string s=readstr(),t=readstr();
	for (int i=1;i<=n;i++){
		if (s[i-1]==t[0]) a[i]=0;
		else if (s[i-1]==t[1]) a[i]=1;
		else a[i]=-1;
	}

	if (t[0]==t[1]){
		ans=k;
		for (int i=1;i<=n;i++)
			ans+=a[i]==0;
		ans=min(ans,n);
		ans=ans*(ans-1)/2;
		cout<<ans<<endl;
		return 0;
	}

	memset(dp,-0x3f3f3f3f,sizeof(dp));

	for (int i=0;i<=n;i++)
		dp[i][0][0]=0;

	for (int i=1;i<=n;i++){
		for (int j=0;j<=k;j++){
			for (int x=0;x<=i;x++){
				dp[i][j][x]=max(dp[i][j][x],dp[i-1][j][x]);
				if (a[i]==0 && x!=0) dp[i][j][x]=max(dp[i][j][x],dp[i-1][j][x-1]);
				if (a[i]==1) dp[i][j][x]=max(dp[i][j][x],dp[i-1][j][x]+x);
				if (j!=0 && x!=0){
					dp[i][j][x]=max(dp[i][j][x],dp[i-1][j-1][x-1]);
					dp[i][j][x]=max(dp[i][j][x],dp[i-1][j-1][x]+x);
				}
			}
		}
	}

	for (int j=0;j<=k;j++){
		for (int x=0;x<=n;x++)
			ans=max(ans,dp[n][j][x]);
	}

	cout<<ans<<endl;
	return 0;
}

1348E Phoenix and Berries

link（*2400）
首先考虑一个显然的朴素 dpdp：设 dpi,j,kdp_{i,j,k} 表示到第 ii 棵树，多出 jj 个红梅和 kk 个蓝莓的答案。
这样的话状态数 O(n3)\mathcal{O(n^3)}，转移 O(n2)\mathcal{O(n^2)}，总复杂度为 O(n5)\mathcal{O(n^5)}，无法通过。
注意到对于每个位置，j+kj+k 在  mod K\bmod K 意义下是恒定不变的，优化一下就可以做到状态数 O(n2)\mathcal{O(n^2)}，转移 O(n)\mathcal{O(n)}，总复杂度 O(n3)\mathcal{O(n^3)} 的 dpdp 了。

是个卡常题，加了火车头，把  mod \bmod 优化掉了之后才能过
但是洛谷不允许 #pragma，所以洛谷提交死活过不了 = =

// 2020.11.21
// Code by LTb

/*省略火车头*/

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN=505;
int n,k;
int a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int sum[MAXN];
int sum1[MAXN],sum2[MAXN];
int qaq[MAXN],qaq1[MAXN],qaq2[MAXN];

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int qwq(int x){return (x>=k)?(x-k):x;}

signed main()

{
	n=read();k=read();
	for (int i=1;i<=n;i++){
		a[i]=read();b[i]=read();
		sum[i]=sum[i-1]+a[i]+b[i];
		sum1[i]=sum1[i-1]+a[i];
		sum2[i]=sum2[i-1]+b[i];

		qaq[i]=sum[i]%k;
		qaq1[i]=sum1[i]%k;
		qaq2[i]=sum2[i]%k;
	}

	for (int i=1;i<=n;i++){
		int tmp1=min(sum1[i]+1,k),tmp2=min(sum1[i-1]+1,k);
		for (int j=0;j<tmp1;j++){
			int l=qwq(qaq[i]+k-j);
			if (l>sum2[i]) continue;
			for (int x=0;x<tmp2;x++){
				int y=qwq(qaq[i-1]+k-x);
				int cnt1=qwq(j-x+k),cnt2=qwq(l-y+k);
				if (cnt1>a[i] || cnt2>b[i] || y>sum2[i-1]) continue;

				dp[i][j]=max(dp[i][j],dp[i-1][x]+(j<x)+(l<y)+(a[i]+b[i]-cnt1-cnt2)/k);
			}
		}
	}

	int ans=0;
	for (int i=0;i<=k;i++)
		ans=max(ans,dp[n][i]);

	printf("%lld\n",ans);
	return 0;
}

1336C Kaavi and Magic Spell

link（*2200）
设 dpi,jdp_{i,j} 表示用 SS 的前 j−i+1j-i+1 个字符填满 Ti∼TjT_i \sim T_j 的方案数
记得答案要 ×2\times 2

// 2020.11.22
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN=3005;
const int MOD=998244353;
int n,m;
char a[MAXN],b[MAXN];
int dp[MAXN][MAXN];

signed main()

{
	string s1=readstr(),s2=readstr();
	n=s1.size();m=s2.size();
	for (int i=1;i<=n;i++)
		a[i]=s1[i-1];

	for (int i=1;i<=m;i++)
		b[i]=s2[i-1];

	for (int i=1;i<=n;i++)
		dp[i][i]=(i>m) || (a[1]==b[i]);

	for (int len=2;len<=n;len++){
		for (int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			dp[i][j]+=dp[i+1][j]*(a[len]==b[i] || i>m)+dp[i][j-1]*(a[len]==b[j] || j>m);
			dp[i][j]%=MOD;
		}
	}

	int ans=0;
	for (int i=m;i<=n;i++)
		ans=(ans+dp[1][i])%MOD;

	cout<<(ans*2)%MOD<<endl;
	return 0;
}

1332F Independent Set

link（*2500）
写了题解

1131E String Multiplication

link（*2300）
设 dpi,jdp_{i,j} 表示 dpdp 到第 ii 个字符串，最长的由字母 jj 组成的子段长度。
预处理 Pi,j,kP_{i,j,k} (k∈{0,1})(k\in \{0,1\})（代码实现中为 youl\texttt{youl} 数组）表示第 ii 个字符串首 / 尾由字母 jj 组成的字段长度。
随便转移
说句闲话：在这题里面第一次使用了 chmax\texttt{chmax}

// 2020.11.28
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
inline void chmax(int &x,int y) {x=max(x,y);}

const int MAXN=100005;
int n;
string a[MAXN];
int siz[MAXN];
int youl[MAXN][30][2];
int dp[MAXN][30];
int ans=1;


signed main()

{
	n=read();
	for (int i=1;i<=n;i++){
		a[i]="N"+readstr();
		siz[i]=a[i].size()-1;
	}

	for (int j=1;j<=n;j++){
		for (int i=1;i<=26;i++){
			char now=i+'a'-1;
			while (youl[j][i][0]<siz[j] && a[j][youl[j][i][0]+1]==now) youl[j][i][0]++;
			while (youl[j][i][1]<siz[j] && a[j][siz[j]-youl[j][i][1]]==now) youl[j][i][1]++;
		}
	}

	for (int i=1;i<=siz[1];i++){
		int cur=i;
		while (cur<siz[1] && a[1][cur+1]==a[1][cur]) cur++;
		chmax(dp[1][a[1][i]-'a'+1],cur-i+1);
		i=cur;
	}

	for (int i=2;i<=n;i++){
		for (int j=1;j<=siz[i];j++){
			int cur=j;
			while (cur<siz[i] && a[i][cur+1]==a[i][cur]) cur++;
			chmax(dp[i][a[i][j]-'a'+1],cur-j+1);
			j=cur;
		}

		for (int j=1;j<=26;j++){
			chmax(dp[i][j],max(youl[i][j][0],youl[i][j][1]));
			if (dp[i-1][j]){
				chmax(dp[i][j],1+youl[i][j][1]+youl[i][j][0]);
				if (youl[i][j][0]==siz[i])
					chmax(dp[i][j],dp[i-1][j]+(dp[i-1][j]+1)*siz[i]);
			}
		}
	}

	for (int i=1;i<=26;i++)
		chmax(ans,dp[n][i]);

	cout<<ans<<endl;
	return 0;
}

1144G Two Merged Sequences

link（*2400）
设 dpi,xdp_{i,x} (x∈{0,1})(x \in \{0,1\})。
dpi,0dp_{i,0} 表示 aia_i 在递减序列中，递增序列末尾元素的最小值
dpi,1dp_{i,1} 表示 aia_i 在递增序列中，递减序列末尾元素的最大值
随便转移
发现了有趣的事情：ref\texttt{ref} 是关键字

// 2020.12.11
// Code by LTb
#include <bits/stdc++.h>
using namespace std;

const int MAXN=200005;
const int INF=0x3f3f3f3f;
int n;
int a[MAXN];
int dp[2][MAXN];
// dp[0][i] 表示当前位置在递减序列中，递增序列的最小值
int refr[2][MAXN];
bool ans[MAXN];

signed main()

{
	n=read();
	for (int i=1;i<=n;i++)
		a[i]=read();

	for (int i=1;i<=n;i++)
		dp[1][i]=-INF,dp[0][i]=INF;

	dp[0][1]=-INF,dp[1][1]=INF;
	for (int i=2;i<=n;i++){
		if (a[i-1]>a[i] && dp[0][i-1]<dp[0][i]) {dp[0][i]=dp[0][i-1];refr[0][i]=0;}
		if (a[i-1]<a[i] && dp[1][i-1]>dp[1][i]) {dp[1][i]=dp[1][i-1];refr[1][i]=1;}
		if (dp[1][i-1]>a[i] && a[i-1]<dp[0][i]) {dp[0][i]=a[i-1];refr[0][i]=1;}
		if (dp[0][i-1]<a[i] && a[i-1]>dp[1][i]) {dp[1][i]=a[i-1];refr[1][i]=0;}
	}

	if (dp[0][n]==INF && dp[1][n]==-INF){
		puts("NO");
		return 0;
	}

	puts("YES");
	int cur=0;
	if (dp[0][n]==INF) cur=1;

	for (int i=n;i>=1;i--){
		ans[i]=!cur;
		cur=refr[cur][i];
	}

	for (int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	cout<<endl;
	return 0;
}

1174E Ehab and the Expected GCD Problem

link（*2500）
是正睿暑假讲过的题（

注意到这个 max⁡{f(p)}\max \{f(p)\} 必然是 1∼n1\sim n 中质因数个数最多的数 的质因数个数
显然这个数一定可以是形如 2k2^k 这样子的
实际上在某些情况下，这个数也可以是 2k−1⋅32^{k-1} \cdot 3，但是其他数是不可能的，因为 5>225>2^2，32>233^2>2^3。
设计一个 dp：dpi,j,kdp_{i,j,k} ( k∈{0,1}k \in \{0,1\} ) 表示当前 dp 到第 ii 个数，前缀 gcd⁡\gcd 中有 jj 个质因子 22，kk 个质因子 33 的方案数。
转移的时候从 i−1i-1 转移到 ii，分几个类讨论：

  • gcd⁡\gcd 不变
  • gcd⁡\gcd 除以 22
  • gcd⁡\gcd 除以 33

注意空间问题

// 2020.12.20
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1000005;
const int MOD=1e9+7;
int n;
int dp[MAXN][22][2];

inline int val(int x,int y){
	return (1<<x)*((y==1)?3:1);
}

signed main()

{
	n=read();
	int lim=log2(n);

	dp[1][lim][0]=1;
	if ((1<<(lim-1))*3<=n) dp[1][lim-1][1]=1;

	for (int i=2;i<=n;i++){
		for (int j=0;j<=lim;j++){
			for (int k=0;k<=1;k++){
				dp[i][j][k]+=1ll*dp[i-1][j][k]*(n/val(j,k)-(i-1))%MOD;
				dp[i][j][k]+=1ll*dp[i-1][j+1][k]*1ll*(n/val(j,k)-n/val(j+1,k))%MOD;
				dp[i][j][k]%=MOD;
				if (!k) dp[i][j][k]+=1ll*dp[i-1][j][k+1]*(n/val(j,k)-n/val(j,k+1))%MOD;
				dp[i][j][k]%=MOD;
			}
		}
	}

	cout<<dp[n][0][0]<<endl;
	return 0;
}

1107E Vasya and Binary String

link（*2400）
非常玄妙的 dp（
（说起来 “dp” 这种东西是不是不应该写成 LaTeX\LaTeX（
看 dls 题解 吧（
感觉这种题就是出题人一拍脑子想出来一个绝妙的 dp 方法，然后用这个方法出了一个题
但是这种思路正常人根本想不到吧（

// 2020.12.26
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN=105;
int n;
bool s[MAXN];
int a[MAXN];
int dp[MAXN][MAXN][MAXN];

signed main()

{
	n=read();
	for (int i=1;i<=n;i++)
		s[i]=readch()=='1';

	for (int i=1;i<=n;i++)
		a[i]=read();

	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			for (int k=0;k+j<=n;k++)
				dp[i][j][k]=-1e15;

	for (int i=1;i<=n;i++)
		for (int j=0;i+j<=n;j++){
			dp[i][i][j]=a[j+1];
		}

	for (int len=2;len<=n;len++){
		for (int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			for (int k=0;k+j<=n;k++)
				chmax(dp[i][j][k],dp[i][j-1][0]+a[k+1]);
			
			for (int k=0;k+j<=n;k++){
				for (int l=i;l<j;l++){
					if (s[l]==s[j]) chmax(dp[i][j][k],dp[i][l][k+1]+dp[l+1][j-1][0]);
				}
			}
		}
	}

	cout<<dp[1][n][0]<<endl;
	return 0;
}
# 专项训练计划 # アルセチ力
【题解】CF1451E1 上一篇
CSP / NOIP 2020 游记 下一篇
Powered by Gridea | © 2019-2020 Theme By HsxyHao
2020-2022 LTb
0%