Educational DP Contest / DP まとめコンテスト部分题解
程序员文章站
2022-04-22 11:49:56
前言: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:
枚举子集既可
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:
首先考虑只求根怎么求,容易得到转移方程
然后再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:
设表示表示这一段没有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,就是剩下多少时的最大值。
考虑怎么排序,就是对于,将他们反过来一定不会更劣。
就是
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:
没有障碍就是
表示到第个障碍的方案数,先用上式算一下,在减去经过其它障碍的情况即可。
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