最近做了一些LOJ的动态规划的题……
区间类动态规划
「一本通 5.1 例 1」石子合并
题解
简单的区间$dp$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=405;
int n;
int a[MAX],sum[MAX];
int f[MAX][MAX],g[MAX][MAX];
int main()
{
scanf("%d",&n);
memset(g,1,sizeof(g));
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),a[i+n]=a[i];
for(int i=1;i<=n*2;++i)
f[i][i]=g[i][i]=0,sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n;++i)
for(int j=1;j<=2*n-i;++j)
for(int k=j;k<j+i;++k)
f[j][j+i]=max(f[j][j+i],f[j][k]+f[k+1][j+i]+sum[j+i]-sum[j-1]),g[j][j+i]=min(g[j][j+i],g[j][k]+g[k+1][j+i]+sum[j+i]-sum[j-1]);
int maxn=0,minn=1e9;
for(int i=1;i<=n;++i)
maxn=max(maxn,f[i][i+n-1]),minn=min(minn,g[i][i+n-1]);
return printf("%d\n%d",minn,maxn),0;
}
「一本通 5.1 例 2」能量项链
题解
简单的区间$dp$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=305;
int n;
int a[MAX],b[MAX];
int f[MAX][MAX];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),a[i+n]=a[i];
for(int i=1;i<2*n;++i)
b[i]=a[i+1];
b[2*n]=a[1];
for(int i=1;i<=n;++i)
for(int j=1;j<=2*n-i;++j)
for(int k=j;k<j+i;++k)
f[j][j+i]=max(f[j][j+i],f[j][k]+f[k+1][j+i]+a[j]*b[k]*b[j+i]);
int maxn=0;
for(int i=1;i<=n;++i)
maxn=max(maxn,f[i][i+n-1]);
return printf("%d",maxn),0;
}
「一本通 5.1 例 3」凸多边形的划分
题解
看成最大值WA了一发……
竟然要用高精度又WA了两发……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=205;
const string inf="99999999999999999999999999999999999999";
int n;
int a[MAX],b[MAX],c[MAX];
string d[MAX];
string f[MAX][MAX];
string operator* (string A,string B)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
string ans="";
int L1=A.length(),L2=B.length(),L3=L1+L2,x=0;
for(int i=1;i<=L1;++i)
b[i]=A[L1-i]-'0';
for(int i=1;i<=L2;++i)
c[i]=B[L2-i]-'0';
for(int i=1;i<=L1;++i)
{
for(int j=1;j<=L2;++j)
a[i+j-1]+=b[i]*c[j]+x,x=a[i+j-1]/10,a[i+j-1]%=10;
a[i+L2]=x,x=0;
}
while(!a[L3]&&L3>1) --L3;
for(int i=L3;i>=1;--i)
ans+=a[i]+'0';
return ans;
}
string operator+ (string A,string B)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
string ans="";
int L1=A.length(),L2=B.length(),L3=max(L1,L2),x=0;
for(int i=1;i<=L1;++i)
b[i]=A[L1-i]-'0';
for(int i=1;i<=L2;++i)
c[i]=B[L2-i]-'0';
for(int i=1;i<=L3;++i)
a[i]=b[i]+c[i]+x,x=a[i]/10,a[i]%=10;
if(x) a[++L3]=x;
for(int i=L3;i>=1;--i)
ans+=a[i]+'0';
return ans;
}
string min(string A,string B)
{
int L1=A.length(),L2=B.length();
if(L1>L2) return B;
if(L1<L2) return A;
for(int i=0;i<L1;++i)
if(A[i]>B[i]) return B;
else if(A[i]<B[i]) return A;
return A;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
cin>>d[i],d[i+n]=d[i];
for(int i=1;i<=2*n;++i)
for(int j=1;j<=2*n;++j)
f[i][j]=inf;
for(int i=1;i<=2*n;++i)
f[i][i+1]=f[i][i]="0";
for(int i=2;i<n;++i)
for(int j=1;j<=2*n-i;++j)
for(int k=j+1;k<j+i;++k)
f[j][j+i]=min(f[j][j+i],f[j][k]+f[k][j+i]+(d[j]*d[k]*d[j+i]));
string minn=inf;
for(int i=1;i<=n;++i)
minn=min(minn,f[i][i+n-1]);
return cout<<minn,0;
}
「一本通 5.1 练习 1」括号配对
题解
前两天刚做过一道类似的……
双个的不匹配就$+2$，一个的就$+1$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=205;
int n;
char s[MAX];
int f[MAX][MAX];
int work(int x,int y)
{
if(s[x]=='['&&s[y]==']') return 0;
if(s[x]=='('&&s[y]==')') return 0;
return 2;
}
int main()
{
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<=n;++i)
{
f[i][i]=1;
for(int j=i+1;j<=n;++j)
f[i][j]=1e9;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n-i;++j)
{
f[j][j+i]=f[j+1][j+i-1]+work(j,j+i);
for(int k=j;k<j+i;++k)
f[j][j+i]=min(f[j][j+i],f[j][k]+f[k+1][j+i]);
}
return printf("%d",f[1][n]),0;
}
「一本通 5.1 练习 2」分离与合体
题解
一样的套路
递归输出方案即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
# include<algorithm>
using namespace std;
const int MAX=305;
struct p{
int l,r;
};
int n;
int a[MAX];
int f[MAX][MAX];
void coutt()
{
queue<p> qu;
qu.push((p){1,n});
while(!qu.empty())
{
p tt=qu.front();
qu.pop();
for(int i=tt.l;i<tt.r;++i)
if(f[tt.l][i]+f[i+1][tt.r]+(a[tt.l]+a[tt.r])*a[i]==f[tt.l][tt.r])
{
qu.push((p){tt.l,i}),qu.push((p){i+1,tt.r}),printf("%d ",i);
break;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n-i;++j)
for(int k=j;k<j+i;++k)
f[j][j+i]=max(f[j][j+i],f[j][k]+f[k+1][j+i]+(a[j]+a[j+i])*a[k]);
return printf("%d\n",f[1][n]),coutt(),0;
}
「一本通 5.1 练习 3」矩阵取数游戏
题解
一行一行的处理即可
依然得用高精度
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=105;
int n,m;
int a[MAX],b[MAX],c[MAX];
string mi_2[MAX];
string A[MAX][MAX],f[MAX][MAX];
string operator* (string A,string B)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
string ans="";
int L1=A.length(),L2=B.length(),L3=L1+L2,x=0;
for(int i=1;i<=L1;++i)
b[i]=A[L1-i]-'0';
for(int i=1;i<=L2;++i)
c[i]=B[L2-i]-'0';
for(int i=1;i<=L1;++i)
{
for(int j=1;j<=L2;++j)
a[i+j-1]+=b[i]*c[j]+x,x=a[i+j-1]/10,a[i+j-1]%=10;
a[i+L2]=x,x=0;
}
while(!a[L3]&&L3>1) --L3;
for(int i=L3;i>=1;--i)
ans+=a[i]+'0';
return ans;
}
string operator+ (string A,string B)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
string ans="";
int L1=A.length(),L2=B.length(),L3=max(L1,L2),x=0;
for(int i=1;i<=L1;++i)
b[i]=A[L1-i]-'0';
for(int i=1;i<=L2;++i)
c[i]=B[L2-i]-'0';
for(int i=1;i<=L3;++i)
a[i]=b[i]+c[i]+x,x=a[i]/10,a[i]%=10;
if(x) a[++L3]=x;
for(int i=L3;i>=1;--i)
ans+=a[i]+'0';
return ans;
}
string max(string A,string B)
{
int L1=A.length(),L2=B.length();
if(L1<L2) return B;
if(L1>L2) return A;
for(int i=0;i<L1;++i)
if(A[i]<B[i]) return B;
else if(A[i]>B[i]) return A;
return A;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>A[i][j];
mi_2[0]="1";
for(int i=1;i<=m;++i)
mi_2[i]=mi_2[i-1]*"2";
string ans="0";
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
for(int k=1;k<=m;++k)
f[j][k]="0";
for(int j=m;j>=1;--j)
for(int l=1;l<=j;++l)
f[l][m-j+l]=max(f[l][m-j+l],f[l+1][m-j+l]+mi_2[j]*A[i][l]),f[j-l+1][m-l+1]=max(f[j-l+1][m-l+1],f[j-l+1][m-l]+mi_2[j]*A[i][m-l+1]);
ans=ans+f[1][m];
}
return cout<<ans,0;
}
树型动态规划
「一本通 5.2 例 1」二叉苹果树
题解
必须保留根节点
简单的树上背包
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e3+5;
struct p{
int x,y,dis;
}c[MAX];
int n,m,num;
int h[MAX],d[MAX],fa[MAX],w[MAX];
int f[MAX][MAX];
void add(int x=0,int y=0,int dis=0)
{
scanf("%d%d%d",&x,&y,&dis);
c[++num]=(p){h[x],y,dis},h[x]=num;
c[++num]=(p){h[y],x,dis},h[y]=num;
}
void dfs(int x=1,int f=0)
{
d[x]=d[f]+1,fa[x]=f;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=f) w[c[i].y]=c[i].dis,dfs(c[i].y,x);
}
void Dfs(int x=1)
{
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa[x]) Dfs(c[i].y);
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa[x]) for(int j=m-(x!=1);j>=0;--j)
for(int k=0;k<=j;++k)
f[x][j]=max(f[x][j],f[x][j-k]+f[c[i].y][k]);
if(x!=1) for(int i=m;i>=1;--i)
f[x][i]=f[x][i-1]+w[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i,add());
dfs(),Dfs();
return printf("%d",f[1][m]),0;
}
「一本通 5.2 例 2」选课
题解
一样的树上背包
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e3+5;
struct p{
int x,y;
}c[MAX];
int n,m,num;
int w[MAX],h[MAX];
int f[MAX][MAX];
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
}
void dfs(int x=0)
{
for(int i=h[x];i;i=c[i].x)
{
dfs(c[i].y);
for(int j=m-bool(x);j>=0;--j)
for(int k=0;k<=j;++k)
f[x][j]=max(f[x][j],f[x][j-k]+f[c[i].y][k]);
}
if(x) for(int i=m;i>=1;--i)
f[x][i]=f[x][i-1]+w[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;++i)
scanf("%d%d",&x,&w[i]),add(x,i);
dfs();
return printf("%d",f[0][m]),0;
}
「一本通 5.2 例 3」数字转换
题解
处理出来关系发现是一棵树
求树上直径即可为什么要用树形dp求直径啊
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=5e4+5;
struct p{
int x,y;
}c[MAX<<1];
int n,m,num,maxn,id;
int h[MAX],d[MAX];
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void ss()
{
for(int i=1,sum;i<=n;++i)
{
sum=0;
for(int j=1;j<=sqrt(i);++j)
if(i%j==0)
{
sum+=j;
if(j!=i/j&&i/j!=i) sum+=i/j;
if(sum>=i) break;
}
if(sum<i) add(i,sum);
}
}
void dfs(int x,int fa=0)
{
d[x]=d[fa]+1;
if(d[x]>maxn) maxn=d[x],id=x;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa) dfs(c[i].y,x);
}
void work()
{
maxn=0,id;
dfs(1),maxn=0,dfs(id),maxn=0,dfs(id);
printf("%d",maxn-1);
}
int main()
{
scanf("%d",&n);
return ss(),work(),0;
}
「一本通 5.2 例 4」战略游戏
题解
$f_{0/1,i}$表示$i$选不选的最少士兵数
因为点权都一样，转移就比较简单了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e3+5;
struct p{
int x,y;
}c[MAX];
int n,num;
int h[MAX];
int f[2][MAX];
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void dfs(int x=0,int fa=0)
{
f[1][x]=1,f[0][x]=0;
int sum=0,minn=1e9;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa) dfs(c[i].y,x),f[1][x]+=min(f[0][c[i].y],f[1][c[i].y]),f[0][x]+=f[1][c[i].y];
}
int main()
{
scanf("%d",&n);
memset(f,1,sizeof(f));
for(int i=1,id,k,x;i<=n;++i)
{
scanf("%d%d",&id,&k);
for(int j=1;j<=k;++j)
scanf("%d",&x),add(id,x);
}
return dfs(),printf("%d",min(f[0][0],f[1][0])),0;
}
「一本通 5.2 例 5」皇宫看守
题解
这题跟上一题差不多，但是点权不相等了
$f_{0/1,0/1,i}$表示$i$选不选、$i$的父亲选不选的最小代价
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e3+5;
struct p{
int x,y;
}c[MAX];
int n,num;
int h[MAX],w[MAX];
int f[2][2][MAX];
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void dfs(int x=1,int fa=0)
{
f[1][1][x]=f[1][0][x]=w[x],f[0][1][x]=f[0][0][x]=0;
int sum=0,minn=1e9,cnt=0,cnt1=0;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa) dfs(c[i].y,x),f[1][1][x]=f[1][0][x]+=min(f[1][1][c[i].y],f[0][1][c[i].y]),f[0][1][x]+=min(f[1][0][c[i].y],f[0][0][c[i].y]),sum+=f[1][0][c[i].y];
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa)
{
++cnt;
if(f[1][0][c[i].y]>f[0][0][c[i].y]) sum+=f[0][0][c[i].y]-f[1][0][c[i].y],++cnt1;
}
if(cnt==cnt1)
{
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa) minn=min(minn,sum-f[0][0][c[i].y]+f[1][0][c[i].y]);
}
else minn=sum;
f[0][0][x]=minn;
}
int main()
{
scanf("%d",&n);
memset(f,1,sizeof(f));
for(int i=1,id,k,m,x;i<=n;++i)
{
scanf("%d%d%d",&id,&k,&m),w[id]=k;
for(int j=1;j<=m;++j)
scanf("%d",&x),add(id,x);
}
return dfs(),printf("%d",min(f[0][0][1],min(f[1][1][1],f[1][0][1]))),0;
}
「一本通 5.2 练习 1」加分二叉树
题解
树形$dp$？区间$dp$？
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=105;
int n;
int a[MAX];
LL f[MAX][MAX];
void coutt(int l,int r)
{
int rt=0;
if(l>r) return;
if(l==r) return void(printf("%d ",l));
for(int i=l;i<=r;++i)
if(f[l][i-1]*f[i+1][r]+a[i]==f[l][r]) {rt=i;break;}
printf("%d ",rt),coutt(l,rt-1),coutt(rt+1,r);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
for(int j=0;j<=n;++j)
f[i][j]=1;
f[i][i]=a[i];
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n-i;++j)
for(int k=j;k<=j+i;++k)
f[j][j+i]=max(f[j][j+i],f[j][k-1]*f[k+1][j+i]+a[k]);
return printf("%lld\n",f[1][n]),coutt(1,n),0;
}
「一本通 5.2 练习 2」旅游规划
题解
没想出树形$dp$……
用点分治的统计方法强行艹过去了qaq 好难调
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e5+5;
struct p{
int x,y;
}c[MAX];
struct q{
int x,y,id;
bool operator< (const q &a)
const{
return x<a.x;
}
}D[MAX];
int n,num,cnt,maxn,id,col,qaq;
int ans[MAX],d[MAX],h[MAX],fa[MAX],bom[MAX];
int use[MAX];
void add(int x=0,int y=0)
{
scanf("%d%d",&x,&y),++x,++y;
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void dfs(int x,int f=0)
{
d[x]=d[f]+1,fa[x]=f;
if(maxn<d[x]) maxn=d[x],id=x;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=f) dfs(c[i].y,x);
}
void GET_NUM(int x,int f,int d,int Col)
{
D[++qaq]=(q){d+1,Col,x},fa[x]=f;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=f) GET_NUM(c[i].y,x,d+1,D[qaq].y);
}
int look(int l,int x)
{
int ans=0,r=qaq;
while(l<=r)
{
int mid(l+r>>1);
if(D[mid].x<x) l=mid+1;
else ans=mid,r=mid-1;
}
return ans;
}
void GET_ANS(int id)
{
while(id&&!use[id]) use[id]=1,ans[++cnt]=id,id=fa[id];
}
void work()
{
dfs(1),maxn=0,dfs(id),maxn=0;
int s1=id,s2;
dfs(id),s2=id,GET_ANS(s2),--maxn;
for(int i=cnt;i>=1;--i)
{
col=0,qaq=0;
for(int j=h[ans[i]];j;j=c[j].x)
if(!use[c[j].y]) GET_NUM(c[j].y,ans[i],0,++col),fa[c[j].y]=0;
D[++qaq]=(q){i-1,0,s2},D[++qaq]=(q){maxn-i+1,0,s1},sort(D+1,D+1+qaq);
int l=1;
while(D[l].x+D[qaq].x<maxn&&l<qaq) ++l;
while(l<qaq&&maxn-D[l].x>=D[l].x)
{
int D3,D1(look(l+1,maxn-D[l].x));
D3=D1;
for(;D[D3].x==maxn-D[l].x;++D3)
if(D[l].y!=D[D3].y)
{
if(!use[D[l].id]) GET_ANS(D[l].id);
if(!use[D[D3].id]) GET_ANS(D[D3].id);
}
++l;
}
}
sort(ans+1,ans+1+cnt);
for(int i=1;i<=cnt;++i)
printf("%d\n",ans[i]-1);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;++i,add());
return work(),0;
}
「一本通 5.2 练习 3」周年纪念晚会
题解
没有上司的舞会？
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e4+5;
struct p{
int x,y;
}c[MAX];
int n,num,rt;
int h[MAX],w[MAX],du[MAX];
int f[2][MAX];
void add(int x=0,int y=0)
{
scanf("%d%d",&y,&x),++du[y];
c[++num]=(p){h[x],y},h[x]=num;
}
void dfs(int x=rt)
{
f[1][x]=w[x];
for(int i=h[x];i;i=c[i].x)
dfs(c[i].y),f[0][x]+=max(f[0][c[i].y],f[1][c[i].y]),f[1][x]+=f[0][c[i].y];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&w[i]);
for(int i=1;i<n;++i,add());
for(int i=1;i<=n;++i)
if(!du[i]) {rt=i;break;}
return dfs(),printf("%d",max(f[0][rt],f[1][rt])),0;
}
「一本通 5.2 练习 4」叶子的染色
题解
从叶子开始求解，$f_{0/1,i}$表示$i$点染成$0$或$1$的最小代价
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e4+5;
struct p{
int x,y;
}c[MAX];
int n,num,m,rt;
int du[MAX],w[MAX],h[MAX];
int f[2][MAX];
void add(int x=0,int y=0)
{
scanf("%d%d",&x,&y),++du[x],++du[y];
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void dfs(int x=rt,int fa=0)
{
if(w[x]!=-1) f[w[x]][x]=1;
else f[0][x]=f[1][x]=1;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa) dfs(c[i].y,x),f[1][x]+=min(f[1][c[i].y]-1,f[0][c[i].y]),f[0][x]+=min(f[0][c[i].y]-1,f[1][c[i].y]);
}
int main()
{
scanf("%d%d",&n,&m);
memset(w,-1,sizeof(w));
memset(f,1,sizeof(f));
for(int i=1;i<=m;++i)
scanf("%d",&w[i]);
for(int i=1;i<n;++i,add());
for(int i=1;i<=n;++i)
if(du[i]>1) {rt=i;break;}
return dfs(),printf("%d",min(f[1][rt],f[0][rt])),0;
}
「一本通 5.2 练习 5」骑士
题解
图是多棵基环树，每个基环树单独处理
去掉环的一条边，然后树形$dp$求解
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e6+5;
struct p{
int x,y;
}c[MAX];
int n,num,s1,s2;
int h[MAX],w[MAX],fa[MAX];
LL f[2][MAX];
bool use[MAX];
void add(int x,int y)
{
fa[y]=x,c[++num]=(p){h[x],y},h[x]=num;
}
void dfs(int x)
{
f[1][x]=w[x],f[0][x]=0,use[x]=1;
for(int i=h[x];i;i=c[i].x)
if(x!=s2||c[i].y!=s1) dfs(c[i].y),f[0][x]+=max(f[0][c[i].y],f[1][c[i].y]),f[1][x]+=f[0][c[i].y];
}
LL GET_ANS(int x)
{
int s=x;
while(fa[x]&&!use[x]) use[x]=1,s1=x,s2=x=fa[x];
dfs(s1);
if(!s2) return max(f[0][s1],f[1][s1]);
LL tt=f[0][s1],qwq=w[s2];
w[s2]=0,dfs(s1),w[s2]=qwq;
return max(tt,f[1][s1]);
}
int main()
{
scanf("%d",&n);
for(int i=1,x;i<=n;++i)
scanf("%d%d",&w[i],&x),add(x,i);
LL ans=0;
for(int i=1;i<=n;++i)
if(!use[i]) ans+=GET_ANS(i);
return printf("%lld",ans),0;
}
数位动态规划
「一本通 5.3 例 1」Amount of Degrees
题解
数位$dp$套路题话说我做过的数位dp都差不多是这个样子的
记忆化搜索即可解决，注意卡边界的问题
代码
# include<iostream>
# include<cstring>
# include<cstdio>
using namespace std;
const int MAX=105;
int X,Y,K,B,num;
int qwq[MAX];
int f[MAX][MAX];
int dfs(int x,int qaq,bool fl)
{
if(qaq<0) return 0;
if(!x) return !qaq;
if(f[x][qaq]!=-1&&fl) return f[x][qaq];
int sum;
if(fl) sum=dfs(x-1,qaq,1)+dfs(x-1,qaq-1,1);
else
{
sum=dfs(x-1,qaq,qwq[x]!=0);
if(qwq[x]) sum+=dfs(x-1,qaq-1,qwq[x]!=1);
}
if(fl) f[x][qaq]=sum;
return sum;
}
int GET_ANS(int x)
{
num=0;
memset(qwq,0,sizeof(qwq));
while(x) qwq[++num]=x%B,x/=B;
return dfs(num,K,0);
}
int main()
{
scanf("%d%d%d%d",&X,&Y,&K,&B);
memset(f,-1,sizeof(f));
return printf("%d",GET_ANS(Y)-GET_ANS(X-1)),0;
}
「一本通 5.3 例 2」数字游戏
题解
还是套路，注意枚举顺序
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=105;
int a,b,num;
int qwq[MAX];
int f[10][MAX];
int dfs(int x,int La,int fl,int qaq)
{
if(!x) return 1;
// if(fl&&f[La][x]!=-1) return f[La][x];
int sum=0;
if(fl) for(int i=La;i<=9;++i)
sum+=dfs(x-1,i,fl,0);
else for(int i=La;i<=qwq[x];++i)
sum+=dfs(x-1,i,i!=qwq[x],0);
if(x!=1&&qaq) sum+=dfs(x-1,1,1,0)+dfs(x-1,10,fl,1);
// if(fl) f[La][x]=sum;
return sum;
}
int GET_ANS(int x)
{
if(!x) return 0;
num=0;
memset(qwq,0,sizeof(qwq));
memset(f,-1,sizeof(f));
while(x) qwq[++num]=x%10,x/=10;
// reverse(qwq+1,qwq+1+num);
return dfs(num,1,0,1);
}
int main()
{
memset(f,-1,sizeof(f));
while(scanf("%d%d",&a,&b)==2) printf("%d\n",GET_ANS(b)-GET_ANS(a-1));
return 0;
}
「一本通 5.3 例 3」Windy 数
题解
因为处理$0$的情况纠结了好一会……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=105;
int A,B,num;
int qwq[MAX];
int f[20][MAX];
int dfs(int x,int La,int fl,int qaq)
{
if(!x) return 1;
if(fl&&f[La][x]!=-1) return f[La][x];
int sum=0;
if(fl)
{
for(int i=La+2;i<=9;++i)
sum+=dfs(x-1,i,1,0);
for(int i=qaq;i<=La-2;++i)
sum+=dfs(x-1,i,1,0);
}
else
{
for(int i=La+2;i<=qwq[x];++i)
sum+=dfs(x-1,i,qwq[x]!=i,0);
for(int i=(x==num||qaq);i<=La-2&&i<=qwq[x];++i)
sum+=dfs(x-1,i,qwq[x]!=i,0);
}
if(x!=1&&qaq) sum+=dfs(x-1,11,1,1);
if(fl) f[La][x]=sum;
return sum;
}
int GET_ANS(int x)
{
if(!x) return 0;
num=0;
while(x) qwq[++num]=x%10,x/=10;
return dfs(num,11,0,1);
}
int main()
{
scanf("%d%d",&A,&B);
memset(f,-1,sizeof(f));
return printf("%d",GET_ANS(B)-GET_ANS(A-1)),0;
}
「一本通 5.3 练习 1」数字游戏
题解
记录一下数位和的记忆化搜索
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=205;
int a,b,n,num;
int qwq[MAX];
int f[MAX][MAX];
int dfs(int x,int tot,int fl)
{
if(!x) return !(tot%n);
if(fl&&f[tot][x]!=-1) return f[tot][x];
int sum=0;
if(fl) for(int i=0;i<=9;++i)
sum+=dfs(x-1,tot+i,1);
else for(int i=0;i<=qwq[x];++i)
sum+=dfs(x-1,tot+i,qwq[x]!=i);
if(fl) f[tot][x]=sum;
return sum;
}
int GET_ANS(int x)
{
// if(!x) return 0;
num=0;
while(x) qwq[++num]=x%10,x/=10;
return dfs(num,0,0);
}
int main()
{
while(scanf("%d%d%d",&a,&b,&n)==3)
{
memset(f,-1,sizeof(f));
printf("%d\n",GET_ANS(b)-GET_ANS(a-1));
}
return 0;
}
「一本通 5.3 练习 2」不要 62
题解
好像是卡边界问题WA了几发？
代码
# include<cstring>
# include<cstdio>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=105;
int n,m,num;
int qwq[MAX];
int f[2][11][MAX];
int dfs(int x,int La,int fl,int qaq)
{
if(!x) return 1;
if(fl&&f[qaq][La][x]!=-1) return f[qaq][La][x];
int sum=0;
if(fl)
{
for(int i=qaq;i<=9;++i)
if(i!=4&&(La!=6||i!=2)) sum+=dfs(x-1,i,1,0);
}
else
{
for(int i=qaq;i<=qwq[x];++i)
if(i!=4&&(La!=6||i!=2)) sum+=dfs(x-1,i,qwq[x]!=i,0);
}
if(x!=1&&qaq) sum+=dfs(x-1,0,1,1);
if(fl) f[qaq][La][x]=sum;
return sum;
}
int GET_ANS(int x)
{
if(!x) return 0;
num=0;
while(x) qwq[++num]=x%10,x/=10;
return dfs(num,0,0,1);
}
int main()
{
memset(f,-1,sizeof(f));
while(scanf("%d%d",&n,&m)==2&&n) printf("%d\n",GET_ANS(m)-GET_ANS(n-1));
return 0;
}
「一本通 5.3 练习 3」恨 7 不成妻
题解
求的是平方和……
$f_{i,j,k}$表示枚举到第$i$位，数位和$\%7$为$j$，正在搜索的这个数$\%7$为$k$的平方和
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<map>
# include<algorithm>
# define LL long long
using namespace std;
const int mod=1e9+7;
struct p{
LL x,tot,sum;
}f[21][10][10];
LL L,R,num;
int qwq[21];
LL qaq[21];
p dfs(int x,int tot,int tt,int TT,int fl)
{
if(!x) return (p){tot&&tt,0,0};
if(fl&&f[x][tot][tt].x!=-1) return f[x][tot][tt];
p sum=(p){0,0,0};
if(fl)
{
for(int i=0;i<=9;++i)
if(i!=7)
{
p Tt=dfs(x-1,(tot+i)%7,(tt*3%7+i)%7,TT*10+i,1);
sum.x=(sum.x+Tt.x)%mod;
sum.tot=(sum.tot+Tt.tot+qaq[x-1]*i%mod*Tt.x%mod)%mod;
sum.sum=(sum.sum+Tt.sum+qaq[x-1]*qaq[x-1]%mod*i%mod*i%mod*Tt.x%mod+qaq[x-1]%mod*2ll%mod*i%mod*Tt.tot%mod)%mod;
}
}
else
{
for(int i=0;i<=qwq[x];++i)
if(i!=7)
{
p Tt=dfs(x-1,(tot+i)%7,(tt*3%7+i)%7,TT*10+i,qwq[x]!=i);
sum.x=(sum.x+Tt.x)%mod;
sum.tot=(sum.tot+Tt.tot+qaq[x-1]*i%mod*Tt.x%mod)%mod;
sum.sum=(sum.sum+Tt.sum+qaq[x-1]*qaq[x-1]%mod*i%mod*i%mod*Tt.x%mod+qaq[x-1]%mod*2ll%mod*i%mod*Tt.tot%mod)%mod;
}
}
// if(x!=1&&qaq) sum=(sum+dfs(x-1,0,0,0,1,1))%mod;
if(fl) f[x][tot][tt]=sum;
return sum;
}
LL GET_ANS(LL x)
{
num=0;
while(x) qwq[++num]=x%10,x/=10;
return dfs(num,0,0,0,0).sum%mod;
}
int main()
{
int T;
scanf("%d",&T);
qaq[0]=1;
for(int i=1;i<=19;++i)
qaq[i]=qaq[i-1]*10%mod;
memset(f,-1,sizeof(f));
while(T--) scanf("%lld%lld",&L,&R),printf("%lld\n",(GET_ANS(R)-GET_ANS(L-1)+mod)%mod);
}
「一本通 5.3 练习 4」数字计数
题解
写的挺麻烦的……借鉴了上一题的方法
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=105;
struct p{
LL num[10],x;
}f[2][MAX],EM;
LL a,b,num;
int qwq[MAX];
bool use[2][MAX];
p operator +(p a,p b)
{
p c=a;
for(int i=0;i<=9;++i)
c.num[i]=a.num[i]+b.num[i];
c.x=a.x+b.x;
return c;
}
p operator -(p a,p b)
{
p c;
for(int i=0;i<=9;++i)
c.num[i]=a.num[i]-b.num[i];
return c;
}
p dfs(int x,int fl,int qaq)
{
if(!x) return EM;
if(fl&&use[qaq][x]) return f[qaq][x];
p sum=EM;
--sum.x;
if(fl) for(int i=qaq;i<=9;++i)
{
p tt=dfs(x-1,1,0);
sum=sum+tt,sum.num[i]+=tt.x;
}
else for(int i=qaq;i<=qwq[x];++i)
{
p tt=dfs(x-1,qwq[x]!=i,0);
sum=sum+tt,sum.num[i]+=tt.x;
}
if(x!=1&&qaq) sum=sum+dfs(x-1,1,1);
if(fl) f[qaq][x]=sum,use[qaq][x]=1;
return sum;
}
p GET_ANS(LL x)
{
num=0;
while(x) qwq[++num]=x%10,x/=10;
return dfs(num,0,1);
}
void coutt(p a)
{
for(int i=0;i<=9;++i)
printf("%lld ",a.num[i]);
}
int main()
{
scanf("%lld%lld",&a,&b),++EM.x;
p qvq=GET_ANS(b),qcq=GET_ANS(a-1);
coutt(qvq-qcq);
}
状态压缩类动态规划
「一本通 5.4 例 1」骑士
题解
壮压基础题……话说不是 互不侵犯 吗
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=(1<<10)+1;
int n,k,num;
int can_[MAX],sum[MAX];
LL f[11][101][MAX];
int GET_NUM(int x)
{
int num=0;
while(x) ++num,x=x&(x-1);
return num;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<(1<<n);++i)
{
bool fl=0;
for(int j=0;j<n;++j)
if((i&(1<<j))&&((i&(1<<(j-1)))||(i&(1<<(j+1))))) {fl=1;break;}
if(!fl) can_[++num]=i,sum[num]=GET_NUM(i);
}
for(int i=1;i<=num;++i)
f[1][sum[i]][i]=1;
for(int i=2;i<=n;++i)
for(int j=1;j<=num;++j)
for(int l=1;l<=num;++l)
for(int h=sum[l];h<=k-sum[j];++h)
if(!(can_[j]&can_[l])&&!((can_[j]<<1)&can_[l])&&!((can_[j]>>1)&can_[l])) f[i][h+sum[j]][j]+=f[i-1][h][l];
LL ans=0;
for(int i=1;i<=num;++i)
ans+=f[n][k][i];
return printf("%lld",ans),0;
}
「一本通 5.4 例 2」牧场的安排
题解
跟上一题差不多，只是需要一行一行的处理
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=(1<<12)+1,mod=1e8;
int n,m;
int num[13];
int sum[13][MAX],can_[13][MAX],f[13][MAX],use[13][13];
int GET_NUM(int x)
{
int num=0;
while(x) ++num,x=x&(x-1);
return num;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=0;j<m;++j)
scanf("%d",&use[i][j]);
for(int i=1;i<=n;++i)
for(int j=0;j<(1<<m);++j)
{
bool fl=0;
for(int l=0;l<m;++l)
if((!use[i][l]&&(j&(1<<l)))||((j&(1<<l))&&((j&(1<<(l-1)))||(j&(1<<(l+1)))))) {fl=1;break;}
if(!fl) can_[i][++num[i]]=j,sum[i][num[i]]=GET_NUM(j);
}
for(int i=1;i<=num[1];++i)
f[1][i]=1;
for(int i=2;i<=n;++i)
for(int j=1;j<=num[i];++j)
for(int l=1;l<=num[i-1];++l)
if(!(can_[i][j]&can_[i-1][l])) f[i][j]=(f[i][j]+f[i-1][l])%mod;
int ans=0;
for(int i=1;i<=num[n];++i)
ans=(ans+f[n][i])%mod;
return printf("%d",ans),0;
}
「一本通 5.4 练习 1」涂抹果酱
题解
思路很简单，只是用三进制表示，写起来挺麻烦的……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e4+5,mod=1e6;
struct p{
int a[7];
}tu[MAX];
int n,m,k,num;
int qaq[11],qwq[11],a[11];
int can_[605],f[605][MAX];
void GET_3(int x)
{
int qvq=x,num=4;
while(qvq&&num>=0)
{
if(qwq[num]<=qvq) tu[x].a[num]=2,qvq-=qwq[num];
if(qaq[num]<=qvq) tu[x].a[num]=1,qvq-=qaq[num];
--num;
}
}
bool look(int x,int y)
{
for(int i=0;i<m;++i)
if(tu[x].a[i]==tu[y].a[i]) return 0;
return 1;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int tt=0;
for(int i=0;i<m;++i)
{
scanf("%d",&a[i]);
if(a[i]==a[i-1]||a[i]==a[i+1]) return printf("0"),0;
}
for(int i=0;i<m;++i)
--a[i];
qaq[0]=1,qwq[0]=2;
for(int i=1;i<11;++i)
qaq[i]=qaq[i-1]*3,qwq[i]=qaq[i]*2;
for(int i=0,fl;i<qaq[m];++i)
{
GET_3(i),fl=0;
// cout<<i<<":";for(int j=0;j<=4;++j)
// cout<<tu[i].a[j]<<" ";
// cout<<endl;
for(int j=0;j<m;++j)
if((j&&tu[i].a[j-1]==tu[i].a[j])||(j!=m-1&&tu[i].a[j+1]==tu[i].a[j])) {fl=1;break;}
if(!fl) can_[++num]=i;
}
for(int i=0;i<m;++i)
tt+=a[i]*qaq[i];
if(k!=1) for(int i=1;i<=num;++i)
f[can_[i]][1]=1;
else f[tt][1]=1;
for(int i=2;i<=n;++i)
if(i==k)
{
for(int j=1;j<=num;++j)
if(look(can_[j],tt)) f[tt][i]=(f[tt][i]+f[can_[j]][i-1])%mod;
}
else
{
if(k==i-1)
{
for(int j=1;j<=num;++j)
if(look(can_[j],tt))
f[can_[j]][i]=(f[can_[j]][i]+f[tt][i-1])%mod;
}
else for(int j=1;j<=num;++j)
for(int l=1;l<=num;++l)
if(look(can_[j],can_[l])) f[can_[j]][i]=(f[can_[j]][i]+f[can_[l]][i-1])%mod;
}
if(k==n) return printf("%d",f[tt][n]);
int ans=0;
for(int i=1;i<=num;++i)
ans=(ans+f[can_[i]][n])%mod;
return printf("%d",ans),0;
}
「一本通 5.4 练习 2」炮兵阵地
题解
也是一道经典题了
$f_{i,j,k}$表示第$i$行，第$i-1$行状态为$j$，第$i-2$行状态为$k$的最多个数，试一下就发现每行最多的满足条件的状态数小于$65$，所以空间不用开很大
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=(1<<10);
int n,m;
int num[105];
int can_[105][MAX],sum[105][MAX];
int f[105][65][65];
char s[105][105];
int GET_NUM(int x)
{
int num=0;
while(x) ++num,x=x&(x-1);
return num;
}
bool look(int x,int y)
{
if(!(x&(1<<y))) return 0;
if((x&(1<<(y-1)))||(x&(1<<(y+1)))||(x&(1<<(y+2)))||(x&(1<<(y-2)))) return 1;
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%s",s[i]);
for(int i=1;i<=n;++i)
for(int j=0;j<(1<<m);++j)
{
bool fl=0;
for(int l=0;l<m;++l)
if((s[i][l]=='H'&&(j&(1<<l)))||look(j,l)) {fl=1;break;}
if(!fl) can_[i][++num[i]]=j,sum[i][num[i]]=GET_NUM(j);
}
for(int i=1;i<=num[1];++i)
f[1][i][i]=sum[1][i];
for(int i=1;i<=num[2];++i)
for(int j=1;j<=num[1];++j)
if(!(can_[2][i]&can_[1][j])) f[2][i][j]=sum[2][i]+sum[1][j];
for(int i=3;i<=n;++i)
for(int j=1;j<=num[i];++j)
for(int k=1;k<=num[i-1];++k)
if(!(can_[i][j]&can_[i-1][k]))
{
int maxn=0;
for(int l=1;l<=num[i-2];++l)
if(!(can_[i][j]&can_[i-2][l])&&!(can_[i-1][k]&can_[i-2][l])) maxn=max(maxn,f[i-1][k][l]);
f[i][j][k]=maxn+sum[i][j];
}
int ans=0;
num[0]=num[1];
for(int i=1;i<=num[n];++i)
for(int j=1;j<=num[n-1];++j)
if(!(can_[n][i]&can_[n-1][j])) ans=max(ans,f[n][i][j]);
return printf("%d",ans),0;
}
「一本通 5.4 练习 3」动物园
题解&代码
单调队列优化动态规划
「一本通 5.5 例 1」滑动窗口
题解
单调队列的简单应用了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e6+5;
int n,k;
int a[MAX],qu[MAX];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int tl=0,hl=1;
for(int i=1;i<=k;++i)
{
while(hl<=tl&&a[qu[tl]]>=a[i]) --tl;
qu[++tl]=i;
}
printf("%d ",a[qu[hl]]);
for(int i=k+1;i<=n;++i)
{
while(hl<=tl&&i-qu[hl]>=k) ++hl;
while(hl<=tl&&a[qu[tl]]>=a[i]) --tl;
qu[++tl]=i,printf("%d ",a[qu[hl]]);
}
printf("\n"),tl=0,hl=1;
for(int i=1;i<=k;++i)
{
while(hl<=tl&&a[qu[tl]]<=a[i]) --tl;
qu[++tl]=i;
}
printf("%d ",a[qu[hl]]);
for(int i=k+1;i<=n;++i)
{
while(hl<=tl&&i-qu[hl]>=k) ++hl;
while(hl<=tl&&a[qu[tl]]<=a[i]) --tl;
qu[++tl]=i,printf("%d ",a[qu[hl]]);
}
return 0;
}
「一本通 5.5 例 2」最大连续和
题解
处理出来前缀和，每次找前面距离不超过$m$的最小的前缀和，也是单调队列基本应用了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e5+5;
int n,m,ans=-1e9;
int a[MAX],sum[MAX],qu[MAX];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
for(int i=1,hl=1,tl=1;i<=n;++i)
{
while(hl<=tl&&i-qu[hl]-1>=m) ++hl;
ans=max(ans,sum[i]-sum[qu[hl]]);
while(hl<=tl&&sum[qu[tl]]>=sum[i]) --tl;
qu[++tl]=i;
}
return printf("%d",ans),0;
}
「一本通 5.5 例 3」修剪草坪
题解
$f_i=max(f_i,f_{j-2}+sum_i-sum_{j-1}),i-j+1\leq k$，可以处理成$f_i=max(f_i,f_{j-2}-sum_{j-1})+sum_i$
所以单调队列维护$f_i-sum_{i+1}$即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+5;
int n,m;
LL ans;
int E[MAX],qu[MAX];
LL f[MAX],sum[MAX];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&E[i]),sum[i]=sum[i-1]+E[i];
for(int i=1,hl=1,tl=1;i<=n;++i)
{
while(hl<=tl&&f[i-1]-sum[i]>=f[qu[tl]-1]-sum[qu[tl]]) --tl;
qu[++tl]=i;
while(hl<=tl&&i-qu[hl]>m) ++hl;
ans=max(ans,f[i]=f[qu[hl]-1]-sum[qu[hl]]+sum[i]);
}
return printf("%lld",ans),0;
}
「一本通 5.5 例 4」旅行问题
题解
环？基本套路破环成链
处理$p_i-d_i$前缀和，如果$sum_i$到$sum_{i+n}$这一段区间里面没有小于$sum_i$的，则说明可以环游一周，逆时针同理
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=2e6+5;
int n;
int qu[MAX],p[MAX],d[MAX];
LL sum[MAX],sum1[MAX];
bool use[MAX];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&p[i],&d[i]),p[i+n]=p[i],d[i+n]=d[i];
for(int i=1;i<=2*n;++i)
sum[i]=sum[i-1]+p[i-1]-d[i-1];
for(int i=2*n;i>=1;--i)
sum1[i]=sum1[i+1]+p[i+1]-d[i];
int hl=1,tl=0;
for(int i=1;i<=n;++i)
{
while(hl<=tl&&sum[qu[tl]]>=sum[i]) --tl;
qu[++tl]=i;
}
for(int i=n+1;i<=2*n;++i)
{
while(hl<=tl&&qu[hl]<=i-n) ++hl;
while(hl<=tl&&sum[qu[tl]]>=sum[i]) --tl;
qu[++tl]=i;
if(sum[qu[hl]]>=sum[i-n]) use[i-n]=1;
}
hl=1,tl=0;
for(int i=2*n;i>=n+1;--i)
{
while(hl<=tl&&sum1[qu[tl]]>=sum1[i]) --tl;
qu[++tl]=i;
}
for(int i=n;i>=1;--i)
{
while(hl<=tl&&qu[hl]>=i+n) ++hl;
while(hl<=tl&&sum1[qu[tl]]>=sum1[i]) --tl;
qu[++tl]=i;
if(sum1[qu[hl]]>=sum1[i+n]) use[i]=1;
}
for(int i=1;i<=n;++i)
if(use[i]) printf("TAK\n");
else printf("NIE\n");
return 0;
}
「一本通 5.5 例 5」Banknotes
题解
原先数据太水了……$O(n\times k\times c)$能卡过……
就是一个多重背包，需要二进制优化不知道跟单调队列有什么关系
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e4+5;
int n,k;
int b[MAX],c[MAX],f[MAX];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
for(int i=1;i<=n;++i)
scanf("%d",&c[i]);
memset(f,1,sizeof(f));
f[0]=0,scanf("%d",&k);
for(int i=1;i<=n;++i)
{
int qwq=c[i];
for(int j=1;qwq;j<<=1)
{
int qaq=min(j,qwq);
for(int l=k;l>=qaq*b[i];--l)
f[l]=min(f[l],f[l-qaq*b[i]]+qaq);
qwq-=qaq;
}
}
return printf("%d",f[k]),0;
}
「一本通 5.5 练习 1」烽火传递
题解
$f_i=min(f_i,f_j+a_i),j\leq i-m$，单调队列维护一下就好了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e5+5;
int n,m;
int a[MAX],qu[MAX],f[MAX];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int hl=1,tl=1;
f[0]=0;
for(int i=1;i<=n;++i)
{
while(hl<=tl&&qu[hl]<i-m) ++hl;
f[i]=f[qu[hl]]+a[i];
while(hl<=tl&&f[qu[tl]]>=f[i]) --tl;
qu[++tl]=i;
}
int ans=1e9;
for(int i=n-m+1;i<=n;++i)
ans=min(ans,f[i]);
return printf("%d",ans),0;
}
「一本通 5.5 练习 2」绿色通道
题解
二分一下空题段长度，然后求最小时间，就跟上一题一样了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=5e4+5;
int n,m;
int a[MAX],f[MAX],qu[MAX];
bool look(int mid)
{
// memset(f,1,sizeof(f));
int hl=1,tl=1;
qu[1]=0;
for(int i=1;i<=n;++i)
{
while(hl<=tl&&qu[hl]<i-mid) ++hl;
f[i]=f[qu[hl]]+a[i];
while(hl<=tl&&f[i]<=f[qu[tl]]) --tl;
qu[++tl]=i;
}
int ans=1e9;
for(int i=n;i>=n-mid+1;--i)
ans=min(ans,f[i]);
return ans<=m;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int l=0,r=n,ans=0;
while(l<=r)
{
int mid(l+r>>1);
if(look(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
return printf("%d",ans-1),0;
}
「一本通 5.5 练习 3」理想的正方形
题解
对于每行处理长度为$n$的区间最大、最小值，$a$遍单调队列即可
对于每行每个区间的答案，从列上在求一遍最大、最小值，这样这一次求的答案都是一个$n\times n$的区域了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e3+5;
int n,m,N;
int qu[MAX];
int a[MAX][MAX],maxn[MAX][MAX],_maxn[MAX][MAX],minn[MAX][MAX],_minn[MAX][MAX];
int main()
{
scanf("%d%d%d",&n,&m,&N);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
for(int i=1,tl,hl;i<=n;++i)
{
hl=1,tl=0;
for(int j=1;j<=m;++j)
{
while(hl<=tl&&qu[hl]<=j-N) ++hl;
while(hl<=tl&&a[i][j]>=a[i][qu[tl]]) --tl;
qu[++tl]=j,maxn[i][j]=a[i][qu[hl]];
}
}
for(int i=1,tl,hl;i<=n;++i)
{
hl=1,tl=0;
for(int j=1;j<=m;++j)
{
while(hl<=tl&&qu[hl]<=j-N) ++hl;
while(hl<=tl&&a[i][j]<=a[i][qu[tl]]) --tl;
qu[++tl]=j,minn[i][j]=a[i][qu[hl]];
}
}
for(int i=1,tl,hl;i<=m;++i)
{
hl=1,tl=0;
for(int j=1;j<=n;++j)
{
while(hl<=tl&&qu[hl]<=j-N) ++hl;
while(hl<=tl&&maxn[j][i]>=maxn[qu[tl]][i]) --tl;
qu[++tl]=j,_maxn[j][i]=maxn[qu[hl]][i];
}
}
for(int i=1,tl,hl;i<=m;++i)
{
hl=1,tl=0;
for(int j=1;j<=n;++j)
{
while(hl<=tl&&qu[hl]<=j-N) ++hl;
while(hl<=tl&&minn[j][i]<=minn[qu[tl]][i]) --tl;
qu[++tl]=j,_minn[j][i]=minn[qu[hl]][i];
}
}
int ans=1e9;
for(int i=N;i<=n;++i)
for(int j=N;j<=m;++j)
ans=min(ans,_maxn[i][j]-_minn[i][j]);
return printf("%d",ans),0;
}
「一本通 5.5 练习 4」股票交易
题解
推出原来的$dp$方程就很好优化了
$f_{i,j}$表示第$i$天，手中有$j$股股票的最大利润，从$f_{i-w-1}$处转移就好了，发现$AS_i,BS_i$的限制就是单调队列的区间限制，这样就可以优化成$O(nm)$的了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e3+5;
int w,t,p;
int ap[MAX],bp[MAX],as[MAX],bs[MAX],qu[MAX];
int f[MAX][MAX];
int main()
{
scanf("%d%d%d",&t,&p,&w);
for(int i=1;i<=t;++i)
scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
memset(f,128,sizeof(f));
for(int i=0;i<=t;++i)
f[i][0]=0;
int ans=0;
for(int i=1;i<=t;++i)
{
for(int j=0;j<=as[i];++j)
f[i][j]=-j*ap[i];
for(int j=0;j<=p;++j)
f[i][j]=max(f[i][j],f[i-1][j]);
if(i<=w) continue;
int hl=1,tl=0;
for(int j=0;j<=p;++j)
{
while(hl<=tl&&qu[hl]<j-as[i]) ++hl;
if(hl<=tl) f[i][j]=max(f[i][j],f[i-w-1][qu[hl]]-j*ap[i]+qu[hl]*ap[i]);
while(hl<=tl&&f[i-w-1][j]+j*ap[i]>=f[i-w-1][qu[tl]]+qu[tl]*ap[i]) --tl;
qu[++tl]=j;
}
hl=1,tl=0;
for(int j=p;j>=0;--j)
{
while(hl<=tl&&qu[hl]>j+bs[i]) ++hl;
if(hl<=tl) f[i][j]=max(f[i][j],f[i-w-1][qu[hl]]-j*bp[i]+qu[hl]*bp[i]);
while(hl<=tl&&f[i-w-1][j]+j*bp[i]>=f[i-w-1][qu[tl]]+qu[tl]*bp[i]) --tl;
qu[++tl]=j;
}
}
for(int i=0;i<=p;++i)
ans=max(ans,f[t][i]);
return printf("%d",ans),0;
}
