当前位置： 移动技术网 > IT编程>开发语言>Java > Educational DP Contest / DP まとめコンテスト部分题解

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

2020年07月15日  | 移动技术网IT编程  | 我要评论

前言：

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网