ZR 集训 Day14 - 动态规划与动态规划常见优化方法 · ooliver

ZR 集训 Day14 - 动态规划与动态规划常见优化方法前言今天转 B 班了，题目比较神秘。 P2150 [NOI2015] 寿司晚宴考虑枚举两个人所选数字的质因子集合。但是 500 以内的素数很多，这时想到根号分治，500 以内的数只会有一个大于 22 的质因数，所以我们把这个质因数单拎出来。22 以内的素数只有 8 个，很好状压。我们把大质因数相等的数放在一起，对于这些数做一个 DP，用两个数组分别表示两个人谁选这些大素数。记得要减去两人都不选的情况。代码： C++ #include using namespace std; const int N=505,M=305; int n,mod,ans; int dp[M][M],f1[M][M],f2[M][M]; int prm[]={2,3,5,7,11,13,17,19}; struct node{ int p,k; bool operator>n>>mod; for(int i=2;i=0;s1--) for(int s2=(1=0;s2--){ if(s1&s2) continue; if((s1&a[i].k)==0) (f1[s1][s2|a[i].k]+=f1[s1][s2])%=mod; if((s2&a[i].k)==0) (f2[s1|a[i].k][s2]+=f2[s1][s2])%=mod; } if(a[i].p==1||a[i].p!=a[i+1].p||i==n){ for(int s1=(1=0;s1--) for(int s2=(1=0;s2--){ if(s1&s2) continue; (dp[s1][s2]=(f1[s1][s2]+f2[s1][s2]-dp[s1][s2])%mod+mod)%=mod; } } } for(int s1=(1=0;s1--) for(int s2=(1=0;s2--){ if(s1&s2) continue; (ans+=dp[s1][s2])%=mod; } cout `#include using namespace std; const int N=505,M=305; int n,mod,ans; int dp[M][M],f1[M][M],f2[M][M]; int prm[]={2,3,5,7,11,13,17,19}; struct node{ int p,k; bool operatorconst node b)const{ return pb.p; } }a[N]; signed main(){ cin>>n>>mod; for(int i=2;in;i++){ int x=i; for(int j=0;j8;j++){ if(x%prm[j]==0){ a[i].k+=(1j); while(x%prm[j]==0) x/=prm[j]; } } a[i].p=x; } sort(a+2,a+1+n); dp[0][0]=1; for(int i=2;in;i++){ if(a[i].p==1||a[i].p!=a[i-1].p||i==2){ memcpy(f1,dp,sizeof dp); memcpy(f2,dp,sizeof dp); } for(int s1=(18)-1;s1>=0;s1--) for(int s2=(18)-1;s2>=0;s2--){ if(s1&s2) continue; if((s1&a[i].k)==0) (f1[s1][s2|a[i].k]+=f1[s1][s2])%=mod; if((s2&a[i].k)==0) (f2[s1|a[i].k][s2]+=f2[s1][s2])%=mod; } if(a[i].p==1||a[i].p!=a[i+1].p||i==n){ for(int s1=(18)-1;s1>=0;s1--) for(int s2=(18)-1;s2>=0;s2--){ if(s1&s2) continue; (dp[s1][s2]=(f1[s1][s2]+f2[s1][s2]-dp[s1][s2])%mod+mod)%=mod; } } } for(int s1=(18)-1;s1>=0;s1--) for(int s2=(18)-1;s2>=0;s2--){ if(s1&s2) continue; (ans+=dp[s1][s2])%=mod; } coutans; return 0; }` P6246 [IOI 2000] 邮局加强版加强版 WQS 二分+决策单调性优化。什么是 WQS 二分？我们设 g(x) 表示建立 x 个邮局所需的代价，发现该函数满足斜率单调，也就是 g(x)-g(x-1)>=g(x+1)-g(x)（这里可以感性理解一下，建 2 个邮局相较于建 1 个邮局代价的变化肯定不少于建 100 个邮局相较于建 99 个邮局代价的变化）。这是我们先不考虑邮局数量的限制，并引入一个常数 C，表示新建一个邮局的代价，就可以得到新的一维 DP 式子： dpi=min{dpj+w(j+1,i)+C}dp_i=min{dp_j+w(j+1,i)+C} 其中 w(i,j) 表示在区间 [i,j] 内新建一个邮局的最小代价。那此时对于一个 C 我们做 DP，会发现：当 C 越大时，最优解建的邮局越少；当 C 越小时，最优解建的邮局越多（这个感性理解一下还是很容易的）。此时我们不妨二分 C，找到最大的 C 使得最优策略刚好建了 m 个邮局，那答案就应该是 dp_n-C\times m。以上就是 WQS 二分的过程了，相当于我们虚构了一个常数出来辅助我们。注意它的使用范围是在原函数是凸函数的情况下。那么以上就是解决这道题的主要步骤了，对于二分的 check，我们需要对于当前的 C 写一个 DP，不难发现其满足决策单调性，用单调队列+二分优化即可。代码： C++ #include using namespace std; #define int long long const int N=5e5+5; int n,m; int a[N],dp[N],sum[N],cnt[N],q[N],opt[N]; int w(int l,int r){ int mid=(l+r)>>1; return (mid-l+1)*a[mid]-(sum[mid]-sum[l-1])+(sum[r]-sum[mid])-(r-mid)*a[mid]; } int calc(int l,int r,int c){ return dp[l]+w(l+1,r)+c; } int bound(int x,int y,int c){ int l=y,r=n,res=y-1; while(l>1; if(calc(x,mid,c)>=calc(y,mid,c)) r=mid-1; else res=mid,l=mid+1; } return res; } int check(int c){ memset(dp,0,sizeof dp); memset(q,0,sizeof q); memset(opt,0,sizeof opt); int l=1,r=1; for(int i=1;i=bound(q[r],i,c)) r--; opt[r]=bound(q[r],i,c),q[++r]=i; } return cnt[n]; } signed main(){ scanf("%d%d",&n,&m); for(int i=1;i>1; if(check(mid)>=m) l=mid+1,ans=dp[n]-m*mid; else r=mid-1; } printf("%lld",ans); return 0; } `#include using namespace std; #define int long long const int N=5e5+5; int n,m; int a[N],dp[N],sum[N],cnt[N],q[N],opt[N]; int w(int l,int r){ int mid=(l+r)>>1; return (mid-l+1)*a[mid]-(sum[mid]-sum[l-1])+(sum[r]-sum[mid])-(r-mid)*a[mid]; } int calc(int l,int r,int c){ return dp[l]+w(l+1,r)+c; } int bound(int x,int y,int c){ int l=y,r=n,res=y-1; while(lr){ int mid=(l+r)>>1; if(calc(x,mid,c)>=calc(y,mid,c)) r=mid-1; else res=mid,l=mid+1; } return res; } int check(int c){ memset(dp,0,sizeof dp); memset(q,0,sizeof q); memset(opt,0,sizeof opt); int l=1,r=1; for(int i=1;in;i++){ while(lr&&opt[l]i) l++; dp[i]=calc(q[l],i,c),cnt[i]=cnt[q[l]]+1; while(lr&&opt[r-1]>=bound(q[r],i,c)) r--; opt[r]=bound(q[r],i,c),q[++r]=i; } return cnt[n]; } signed main(){ scanf("%d%d",&n,&m); for(int i=1;in;i++) scanf("%d",a+i); sort(a+1,a+1+n); for(int i=1;in;i++) sum[i]=a[i]+sum[i-1]; int l=0,r=1e9,ans; while(lr){ int mid=(l+r)>>1; if(check(mid)>=m) l=mid+1,ans=dp[n]-m*mid; else r=mid-1; } printf("%lld",ans); return 0; }`