欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  网络运营

Educational DP Contest / DP まとめコンテスト部分题解

程序员文章站 2022-07-08 17:38:16
前言：dp太差，开个大坑因为太多题了，只做现场AC小于300的题...

前言：

dp太差，开个大坑
因为太多题了，只做现场AC小于200的题
比较好的题可能会单独写
太水的可能也不写
顺序随意

R - Walk：

倍增floyd模板题
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream> 
#define LL long long
using namespace std;
const LL mod=1e9+7;
LL n,k;
struct node{
	LL a[50][50];
	node() {memset(a,0,sizeof(a));}
}e;
node operator * (node a,node b)
{
	node ans;
	for(LL k=0;k<n;k++)
		for(LL i=0;i<n;i++)	
			for(LL j=0;j<n;j++)
				(ans.a[i][j]+=a.a[i][k]*b.a[k][j]%mod)%=mod;
	return ans;
}
node operator ^ (node a,LL b)
{
	node ans;
	for(LL i=0;i<n;i++) ans.a[i][i]=1;
	while(b)
	{
		if(b&1) ans=ans*a;
		a=a*a;b>>=1;
	}
	return ans;
}
int main()
{
	scanf("%lld %lld",&n,&k);
	for(LL i=0;i<n;i++)
		for(LL j=0;j<n;j++) scanf("%lld",&e.a[i][j]);
	e=e^k;
	LL ans=0;
	for(LL i=0;i<n;i++)
		for(LL j=0;j<n;j++) (ans+=e.a[i][j])%=mod;
	printf("%lld",ans);
}

U - Grouping：

O(n3)O(n^3)枚举子集既可
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
LL n,a[25][25],g[1<<16],bin[1<<16],f[1<<16];
int main()
{
	scanf("%lld",&n);
	for(LL i=0;i<n;i++) bin[1<<i]=i;
	for(LL i=0;i<n;i++)
		for(LL j=0;j<n;j++) scanf("%lld",&a[i][j]);
	for(LL i=1;i<1<<n;i++)
	{
		LL u=i&(-i),x=bin[u],t=i^u;g[i]=g[t];
		for(LL j=0;j<n;j++)
			if((1<<j)&t) g[i]+=a[j][x];
	}
	for(LL i=1;i<1<<n;i++)
		for(LL j=i;j;j=(j-1)&i) f[i]=max(f[i],g[j]+f[i^j]);
	printf("%lld",f[(1<<n)-1]);
}

T - Permutation：

给个加强版：传送门
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const int mod=1e9+7;
int n,f[3010][3010],sum[3010][3010];
char s[3010];
int main()
{
	scanf("%d",&n);getchar();
	scanf("%s",s+1);
	f[1][1]=sum[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(s[i-1]=='<') f[i][j]=sum[i-1][j-1];
			else f[i][j]=(sum[i-1][i-1]-sum[i-1][j-1])%mod;
		}
		for(int j=1;j<=i;j++) sum[i][j]=(sum[i][j-1]+f[i][j])%mod;//printf("%d ",f[i][j]);printf("\n");
	}
	printf("%d",(sum[n][n]+mod)%mod);
}

V - Subtree：

首先考虑只求根怎么求，容易得到转移方程f[x]=Πy∈sonx(f[y]+1)f[x]=\Pi_{y\in son_x}(f[y]+1)
然后再dfs一次去换根即可。
然而这题没有逆元，所以用前缀积后缀积实现。
code：

#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
vector<LL> vec[100010],l[100010],r[100010];
LL n,mod;
struct node{
	LL y,next;
}a[200010];LL len=0,last[100010],f[100010];
LL ans[100010];
void ins(LL x,LL y)
{
	a[++len].y=y;
	a[len].next=last[x];last[x]=len;
}
void dfs(LL x,LL fa)
{
	f[x]=1;LL tot=0;
	for(LL i=last[x];i;i=a[i].next)
	{
		LL y=a[i].y;
		if(y==fa) continue;
		dfs(y,x);
		vec[x].push_back(y);
		l[x].push_back(0);r[x].push_back(0);
		(f[x]*=(f[y]+1))%=mod;
		tot++;
	}
	for(LL i=0;i<tot;i++)
	{
		l[x][i]=(i==0)?1:l[x][i-1];
		(l[x][i]*=(f[vec[x][i]]+1))%=mod;
	}
	for(LL i=tot-1;i>=0;i--)
	{
		r[x][i]=(i==tot-1)?1:r[x][i+1];
		(r[x][i]*=(f[vec[x][i]]+1))%=mod;
	}
}
void solve(LL x,LL c)
{
	ans[x]=(f[x]*(c+1))%mod;
	for(LL i=0;i<vec[x].size();i++)
	{
		LL y=vec[x][i];
		LL c1=(i==0)?1:l[x][i-1];
		LL c2=(i==vec[x].size()-1)?1:r[x][i+1];
		solve(y,(c+1)*c1%mod*c2%mod);
	}
}
int main()
{
	scanf("%lld %lld",&n,&mod);
	for(LL i=1;i<n;i++)
	{
		LL x,y;scanf("%lld %lld",&x,&y);
		ins(x,y);ins(y,x);
	}
	dfs(1,0);solve(1,0);
	for(LL i=1;i<=n;i++) printf("%lld\n",ans[i]);
}

W - Intervals：

设f[i][j]f[i][j]表示表示i ji~j这一段没有1的最大值。
将操作排序，降成一维，线段树维护即可。
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
LL n,m,f[2010];
struct node{
	LL l,r,a;
}a[200010];
bool cmp(node a,node b) {return a.r<b.r;}
struct trnode{
	LL lc,rc,c,u;
}tr[400010];LL tot=0;
LL bt(LL l,LL r)
{
	LL x=++tot;
	if(l!=r)
	{
		LL mid=(l+r)/2;
		tr[x].lc=bt(l,mid);
		tr[x].rc=bt(mid+1,r);
	}
	return x;
}
void update(LL x)
{
	LL lc=tr[x].lc,rc=tr[x].rc,c=tr[x].u;
	tr[lc].c+=c;tr[rc].c+=c;
	tr[lc].u+=c;tr[rc].u+=c;
	tr[x].u=0;
}
void change(LL x,LL l,LL r,LL fl,LL fr,LL c)
{
	if(l==fl&&r==fr) {tr[x].c+=c;tr[x].u+=c;return;}
	LL mid=(l+r)/2;
	if(tr[x].u!=0) update(x);
	if(fr<=mid) change(tr[x].lc,l,mid,fl,fr,c);
	else if(fl>mid) change(tr[x].rc,mid+1,r,fl,fr,c);
	else change(tr[x].lc,l,mid,fl,mid,c),change(tr[x].rc,mid+1,r,mid+1,fr,c);
	tr[x].c=max(tr[tr[x].lc].c,tr[tr[x].rc].c);
}
LL findans(LL x,LL l,LL r,LL fl,LL fr)
{
	if(l==fl&&r==fr) return tr[x].c;
	LL mid=(l+r)/2;
	if(tr[x].u!=0) update(x);
	if(fr<=mid) return findans(tr[x].lc,l,mid,fl,fr);
	if(fl>mid) return findans(tr[x].rc,mid+1,r,fl,fr);
	return max(findans(tr[x].lc,l,mid,fl,mid),findans(tr[x].rc,mid+1,r,mid+1,fr));
}
int main()
{
	scanf("%lld %lld",&n,&m);
	for(LL i=1;i<=m;i++) scanf("%lld %lld %lld",&a[i].l,&a[i].r,&a[i].a);
	sort(a+1,a+m+1,cmp);
	LL p=0;bt(0,n);
	for(LL i=1;i<=n;i++)
	{
		change(1,0,n,i,i,findans(1,0,n,0,i-1));
		while(p<m&&a[p+1].r==i) p++,change(1,0,n,a[p].l,a[p].r,a[p].a);
	}
	printf("%lld",findans(1,0,n,0,n));
}

X - Tower：

这种题显然可以排序后dp，f[i]f[i]就是剩下多少时的最大值。
考虑怎么排序，就是对于i,ji,j，将他们反过来一定不会更劣。
就是as−bw&gt;bs−awa_s-b_w&gt;b_s-a_w
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
LL f[10010];
struct node{int w,s,v;}a[1010];
int n,m;
bool cmp(node a,node b) {return a.s-b.w>b.s-a.w;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d %d %d",&a[i].w,&a[i].s,&a[i].v);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		for(int j=a[i].w;j<=10000;j++) f[min(j-a[i].w,a[i].s)]=max(f[min(j-a[i].w,a[i].s)],f[j]+a[i].v);
		f[a[i].s]=max(f[a[i].s],(LL)a[i].v);
	}
	LL ans=0;
	for(int i=0;i<=10000;i++) ans=max(ans,f[i]);
	printf("%lld",ans);
}

Y - Grid 2：

没有障碍就是Cx+y−2x−1C_{x+y-2}^{x-1}
f[i]f[i]表示到第ii个障碍的方案数，先用上式算一下，在减去经过其它障碍的情况即可。
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const LL mod=1e9+7;
LL fac[200010],inv[200010];
void pre()
{
	inv[0]=inv[1]=fac[0]=fac[1]=1;
	for(LL i=2;i<=200000;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(LL i=2;i<=200000;i++) inv[i]=inv[i-1]*inv[i]%mod,fac[i]=fac[i-1]*i%mod;
}
LL C(LL m,LL n) {return fac[m]*inv[m-n]%mod*inv[n]%mod;}
LL n,m,k,f[3010];
struct node{LL x,y;}a[3010];
bool cmp(node a,node b) {return a.x==b.x?a.y<b.y:a.x<b.x;}
int main()
{
	pre();
	scanf("%lld %lld %lld",&n,&m,&k);
	for(LL i=1;i<=k;i++)
	{
		scanf("%lld %lld",&a[i].x,&a[i].y);
		if((a[i].x==1&&a[i].y==1)||(a[i].x==n&&a[i].y==m)) return puts("0"),0;
	}
	a[++k].x=n;a[k].y=m;
	sort(a+1,a+k+1,cmp);
	for(LL i=1;i<=k;i++)
	{
		f[i]=C(a[i].x+a[i].y-2,a[i].x-1);
		for(LL j=1;j<i;j++)
			if(a[j].x<=a[i].x&&a[j].y<=a[i].y)
			{
				LL x=a[i].x-a[j].x,y=a[i].y-a[j].y;
				(f[i]-=f[j]*C(x+y,x))%=mod;
			}
		//printf("%lld %lld %lld\n",a[i].x,a[i].y,f[i]);
	}
	printf("%lld",(f[k]+mod)%mod);
}

本文地址：https://blog.csdn.net/qq_36808030/article/details/85986560

相关标签： dp atcoder

上一篇： 随心拔插主板上的Type-C到底是什么？

下一篇： 华硕主板双11销量/销售额全网第一：B360单日破万

推荐阅读