【做題記錄】2025暑假-dp專(zhuān)題
A. The Bakery
設(shè) \(dp_{i,j}\) 表示 \(i\) 為第 \(j\) 段的中點(diǎn)的最大價(jià)值，容易寫(xiě)出轉(zhuǎn)移式：\(dp_{i,j}=\max_{k=0}^{i-1}\{dp_{k,j-1}+cost[k+1,i]\}\)。看到 \(\max\) 可以考慮線(xiàn)段樹(shù)優(yōu)化 DP，因此我們需要在 \(O(\log n)\) 的時(shí)間內(nèi)求出 \(cost\)。考慮對(duì)于 \(i\)，它的值上一次出現(xiàn)的位置為 \(pre_i\)，那么 \([pre_i+1,i]\) 都會(huì)有 \(1\) 的貢獻(xiàn)。于是進(jìn)行一個(gè)區(qū)間加操作即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=4e4+5;
int n,m,a[maxn],pre[maxn],pos[maxn];
struct{
int tr[maxn<<2],tag[maxn<<2];
il void pushup(int id){
tr[id]=max(tr[lid],tr[rid]);
}
il void pushtag(int id,int v){
tr[id]+=v,tag[id]+=v;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r){
tr[id]=tag[id]=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il void add(int id,int L,int R,int l,int r,int v){
if(L>=l&&R<=r){
pushtag(id,v);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid,l,r,v);
}
if(r>mid){
add(rid,mid+1,R,l,r,v);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return tr[id];
}
pushdown(id);
int mid=(L+R)>>1,res=0;
if(l<=mid){
res=max(res,query(lid,L,mid,l,r));
}
if(r>mid){
res=max(res,query(rid,mid+1,R,l,r));
}
return res;
}
}S[2];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pos[a[i]];
pos[a[i]]=i;
}
for(int i=1,j=1;i<=m;i++,j^=1){
S[j].build(1,0,n);
for(int k=1;k<=n;k++){
S[j^1].add(1,0,n,pre[k],k-1,1);
S[j].add(1,0,n,k,k,S[j^1].query(1,0,n,0,k-1));
}
}
cout<<S[m&1].query(1,0,n,n,n);
return 0;
}
}
signed main(){return asbt::main();}
B. Birds
設(shè) \(f_{i,j}\) 表示走到第 \(i\) 棵樹(shù)，召喚了 \(j\) 只鳥(niǎo)的最大剩余魔法。時(shí)間復(fù)雜度 \(O((\sum c_i)^2)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e3+5;
int n,W,B,X,a[maxn],b[maxn],sa[maxn],f[maxn][maxn*10];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>W>>B>>X;
for(int i=1;i<=n;i++){
cin>>a[i];
sa[i]=sa[i-1]+a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
memset(f,-1,sizeof(f));
f[0][0]=W;
for(int i=1;i<=n;i++){
for(int j=0;j<=sa[i];j++){
for(int k=0;k<=min(a[i],j);k++){
if(~f[i-1][j-k]&&f[i-1][j-k]>=b[i]*k){
f[i][j]=max(f[i][j],f[i-1][j-k]-b[i]*k+X);
}
}
f[i][j]=min(f[i][j],W+B*j);
}
}
for(int i=sa[n];;i--){
if(~f[n][i]){
cout<<i;
break;
}
}
return 0;
}
}
signed main(){return asbt::main();}
C. Helping People
區(qū)間不交錯(cuò)，這讓我們聯(lián)想到建樹(shù)。然而這是一個(gè)森林，再建一個(gè)虛點(diǎn)即可。
然后考慮樹(shù)形 DP，設(shè) \(f_{u,i}\) 表示 \(u\) 的區(qū)間，最大值為 \(i\) 的概率。顯然時(shí)空都會(huì)爆炸，考慮 \(i\in[mx_u,mx_u+m]\)，其中 \(mx_u=\max[l_u,r_u]\)，因此設(shè) \(f_{u,i}\) 表示 \(u\) 的區(qū)間，最大值為 \(mx_u+i\) 的概率。于是有轉(zhuǎn)移：
時(shí)間復(fù)雜度 \(O(m^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5,maxm=5e3+5;
int n,m,rt,a[maxn],deg[maxn];
double f[maxm][maxm];
vector<int> E[maxn],e[maxn];
queue<int> q;
struct{
int l,r,mx;
double p;
}b[maxm];
struct{
int st[maxn][22],Log[maxn];
il void build(){
for(int i=2;i<=n;i++){
Log[i]=Log[i>>1]+1;
}
for(int i=1;i<=n;i++){
st[i][0]=a[i];
}
for(int j=1;j<=Log[n];j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
il int query(int l,int r){
int p=Log[r-l+1];
return max(st[l][p],st[r-(1<<p)+1][p]);
}
}ST;
il void dfs(int u){
// cout<<u<<" "<<b[u].l<<" "<<b[u].r<<" "<<b[u].p<<"\n";
for(int v:e[u]){
dfs(v);
}
for(int i=0;i<=m;i++){
double p1=b[u].p,p2=1-p1;
for(int v:e[u]){
int t1=i+b[u].mx-b[v].mx-1,t2=t1+1;
p1*=f[v][min(t1,m)];
p2*=f[v][min(t2,m)];
}
f[u][i]=i?p1+p2:p2;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
// cerr<<"6666666\n";
ST.build();
for(int i=1;i<=m;i++){
// cin>>b[i].l>>b[i].r>>b[i].p;
scanf("%d%d%lf",&b[i].l,&b[i].r,&b[i].p);
}
b[++m].l=1,b[m].r=n,b[m].p=0;
for(int i=1;i<=m;i++){
b[i].mx=ST.query(b[i].l,b[i].r);
for(int j=1;j<=m;j++){
if(i==j){
continue;
}
if(b[i].l==b[j].l&&b[i].r==b[j].r){
if(i<j){
E[i].pb(j),deg[j]++;
}
else{
E[j].pb(i),deg[i]++;
}
}
else if(b[i].l<=b[j].l&&b[i].r>=b[j].r){
E[i].pb(j),deg[j]++;
}
else if(b[i].l>=b[j].l&&b[i].r<=b[j].r){
E[j].pb(i),deg[i]++;
}
}
}
for(int i=1;i<=m;i++){
if(!deg[i]){
rt=i;
q.push(i);
break;
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int v:E[u]){
if(--deg[v]==0){
e[u].pb(v);
q.push(v);
}
}
}
dfs(rt);
// for(int i=1;i<=m;i++){
// for(int j=0;j<=m;j++){
// cout<<f[i][j]<<" ";
// }
// cout<<"\n";
// }
double ans=0;
for(int i=0;i<=m;i++){
ans+=(f[rt][i]-(i?f[rt][i-1]:0))*(i+b[rt].mx);
}
printf("%.8f",ans);
return 0;
}
}
int main(){return asbt::main();}
D. Game on Sum (Easy Version)
我們發(fā)現(xiàn)，每一步的操作都和前面的操作無(wú)關(guān)，只和后面的操作有關(guān)，即有后效性而無(wú)前效性，于是考慮倒著 DP。設(shè) \(f_{i,j}\) 表示 \(n=i\)，\(m=j\) 時(shí)的答案，于是有 \(f_{i,j}=\frac{f_{i-1,j-1}+f_{i-1,j}}{2}\)。邊界條件為 \(f_{i,0}=0\)，\(f_{i,i}=i\times K\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e3+5,mod=1e9+7,_2=5e8+4;
int T,n,m,kk,f[maxn][maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m>>kk;
for(int i=1;i<=n;i++){
for(int j=1;j<=min(i-1,m);j++){
f[i][j]=(f[i-1][j-1]+f[i-1][j])*1ll*_2%mod;
}
if(i<=m){
f[i][i]=i*1ll*kk%mod;
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout<<f[i][j]<<" ";
// }
// cout<<"\n";
// }
cout<<f[n][m]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
E. Positions in Permutations
考慮二項(xiàng)式反演，設(shè) \(F_i\) 表示欽定有 \(i\) 個(gè)位置滿(mǎn)足條件，其它的隨便選的方案數(shù)。于是 \(ans=\sum_{i=K}^{n}(-1)^{i-m}{i\choose m}F_i\)。考慮 DP 求出 \(F\)。
設(shè) \(f_{i,j,0/1,0/1}\) 表示考慮了前 \(i\) 個(gè)位置，有 \(j\) 個(gè)位置滿(mǎn)足條件，有沒(méi)有選 \(i\)，有沒(méi)有選 \(i+1\) 的方案數(shù)。注意這里只考慮那些滿(mǎn)足條件的位置，而不考慮不滿(mǎn)足條件的位置，即不滿(mǎn)足的位置此時(shí)是空的。不難得出 \(F_i=(f_{n,i,0,0}+f_{n,i,1,0})\times(n-i)!\)。轉(zhuǎn)移方程考慮在 \(i\) 這一位填 \(i-1\)、填 \(i+1\) 或不填即可。
因?yàn)?CF 目前壞了所以暫時(shí)不能保證代碼正確性，先不貼 code 了。（F 題同）
upd：CF 好了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e3+5,mod=1e9+7;
int n,m,fac[maxn],C[maxn][maxn],f[maxn][maxn][2][2];
il int add(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il int sub(int x,int y){
return x<y?x-y+mod:x-y;
}
il void upd(int &x,int y){
x=x+y<mod?x+y:x+y-mod;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
fac[0]=C[0][0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
f[1][0][0][0]=f[1][1][0][1]=1;
for(int i=2;i<=n;i++){
f[i][0][0][0]=1;
for(int j=1;j<=i;j++){
upd(f[i][j][0][0],f[i-1][j-1][0][0]);
upd(f[i][j][1][0],f[i-1][j-1][0][1]);
upd(f[i][j][0][1],add(f[i-1][j-1][0][0],f[i-1][j-1][1][0]));
upd(f[i][j][1][1],add(f[i-1][j-1][0][1],f[i-1][j-1][1][1]));
upd(f[i][j][0][0],add(f[i-1][j][0][0],f[i-1][j][1][0]));
upd(f[i][j][1][0],add(f[i-1][j][0][1],f[i-1][j][1][1]));
}
}
int ans=0;
for(int i=m;i<=n;i++){
ans=((i-m)&1?sub:add)(ans,(f[n][i][0][0]+f[n][i][1][0])*1ll*C[i][m]%mod*fac[n-i]%mod);
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
F. Divan and Kostomuksha (easy version)
設(shè) \(cnt_i\) 表示能被 \(i\) 整除的元素?cái)?shù)量，\(dp_i\) 表示全局 \(\gcd\) 為 \(i\) 時(shí)的最大權(quán)值。有方程 \(dp_i=\max_{i\mid j}\{dp_j+i\times(cnt_i-cnt_j)\}\)。時(shí)間復(fù)雜度 \(O(V\ln V)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e6+5,m=5e6;
int n,cnt[maxn],dp[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,x;i<=n;i++){
cin>>x;
cnt[x]++;
}
for(int i=1;i<=m;i++){
for(int j=i<<1;j<=m;j+=i){
cnt[i]+=cnt[j];
}
}
for(int i=m;i;i--){
dp[i]=cnt[i]*i;
for(int j=i<<1;j<=m;j+=i){
dp[i]=max(dp[i],dp[j]+i*(cnt[i]-cnt[j]));
}
}
cout<<dp[1];
return 0;
}
}
signed main(){return asbt::main();}
G. Future Failure
分析這個(gè)游戲先手必勝的條件，發(fā)現(xiàn)如果此字符串有偶數(shù)種不同的排列，先手是必勝的。原因是，如果有一個(gè)刪字母的方案使先手必勝，則先手必勝；如果沒(méi)有，那么雙方一定不停地重排，又因?yàn)橛信紨?shù)種排列，所以還是先手必勝的。
然后分析奇數(shù)種排列的情況。首先，如果雙方不停地重排，顯然是先手不勝的，于是先手必然要?jiǎng)h字符。一個(gè)字符串的排列個(gè)數(shù)為 \(\frac{n!}{\prod a_i!}\)，注意到刪一個(gè)字符 \(i\) 相當(dāng)于給這個(gè)東西乘上 \(\frac{a_i}{n}\)，不會(huì)影響奇偶性，于是雙方都不停地刪字符，于是 \(n\) 為奇數(shù)先手必勝，為偶數(shù)先手必?cái) ?/p>
那么我們可以得到一個(gè)大致思路：如果 \(n\) 為奇數(shù)那么直接輸出 \(k^n\)，否則 DP 求出先手必勝，即排列數(shù)為偶數(shù)的方案數(shù)。然而這實(shí)際上不好求，正難則反。考慮分析 \(\frac{n!}{\prod a_i!}\) 的奇偶性，即分子與分母包含 \(2\) 的個(gè)數(shù)。對(duì)于 \(n!\)，它包含的 \(2\) 的個(gè)數(shù)即為 \(\sum_{i\in\mathbb{N}^*}\lfloor\frac{n}{i}\rfloor\)。又因?yàn)?\(\lfloor\frac{a}{x}\rfloor+\lfloor\frac{b}{x}\rfloor\le\lfloor\frac{a+b}{x}\rfloor\)，于是我們的要求即為：
考慮將 \(n\) 拆成二進(jìn)制，對(duì)于最高位，顯然要求恰有一個(gè) \(a_i\) 該位為 \(1\)。進(jìn)而，我們實(shí)際上要求的就是對(duì)于 \(n\) 中的每個(gè) \(1\)，都恰有一個(gè) \(a_i\) 該位為 \(1\)，而對(duì)于每個(gè) \(0\) 則要求所有 \(a_i\) 該位都是 \(0\)。于是可以 DP 了。設(shè) \(f_{x,S}\) 表示考慮前 \(x\) 個(gè) \(a\)，還剩下 \(S\) 個(gè)字符分配的\(\prod\frac{1}{a_i!}\) 的和。故有轉(zhuǎn)移：\(f_{x,S}\leftarrow f_{x-1,S+T}\times\frac{1}{T!}\)。不過(guò)枚舉子集轉(zhuǎn)移時(shí)間復(fù)雜度較大，可以欽定這個(gè)位置選擇 \(\operatorname{lowbit}(S)\)，最后再乘上排列數(shù)。代碼中使用的是記憶化搜索，為了方便轉(zhuǎn)移，傳的參數(shù)實(shí)際上是 \(k-x\) 和 \(n-S\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int n,m,mod,fac[maxn],inv[maxn],f[30][maxn];
il int qpow(int x,int y){
int res=1;
for(;y;y>>=1,x=x*1ll*x%mod){
if(y&1){
res=res*1ll*x%mod;
}
}
return res;
}
il int lowbit(int x){
return x&-x;
}
il int dfs(int x,int S){
// cout<<x<<" "<<S<<"\n";
if(~f[x][S]){
return f[x][S];
}
if(!S){
int res=1;
for(int i=1;i<=x;i++){
res=res*1ll*(m-i+1)%mod;
}
return f[x][S]=res;
}
int res=0,U=S-lowbit(S);
for(int T=U;;T=(T-1)&U){
res=(res+inv[S-T]*1ll*dfs(x+1,T))%mod;
if(!T){
break;
}
}
return f[x][S]=res;
}
il void init(int n=3e5){
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[n]=qpow(fac[n],mod-2);
for(int i=n;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>mod;
init();
memset(f,-1,sizeof(f));
// puts("666");
// cout<<dfs(0,n)*1ll*fac[n]%mod<<"\n";
cout<<(qpow(m,n)+(n&1?0:mod-dfs(0,n)*1ll*fac[n]%mod))%mod;
return 0;
}
}
int main(){return asbt::main();}
H. Tavas in Kansas
首先從 \(S\) 和 \(T\) 各跑一遍最短路，并將距離離散化出來(lái)。注意到如果 \(A\) 要選 \(x\) 和 \(y\)，而 \(x\) 離 \(A\) 又比 \(y\) 近，則 \(x\) 一定不會(huì)在 \(y\) 之后選。于是到現(xiàn)在這個(gè)問(wèn)題已經(jīng)和圖論沒(méi)有關(guān)系了。
考慮 DP。設(shè) \(f_{0/1,i,j}\) 表示目前的先手是誰(shuí)，還剩下 \(\operatorname{dis}(S)\ge i\land\operatorname{dis}(T)\ge j\) 的點(diǎn)時(shí)當(dāng)前的先手的最大得分，記 \(cnt_{i,j}\) 為符合上述條件的點(diǎn)數(shù)，\(sum_{i,j}\) 為這些點(diǎn)的權(quán)值和。于是有方程：
遞推計(jì)算轉(zhuǎn)移點(diǎn)，后綴最小值優(yōu)化即可做到 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=2e3+5;
int n,m,S,T,cs,ct,a[maxn],dis[2][maxn],lsh[maxn];
int cnt[maxn][maxn],sum[maxn][maxn];
int f[2][maxn][maxn],g[2][maxn][maxn],p[2][maxn][maxn];
bool vis[maxn];
vector<pii> e[maxn];
priority_queue<pii> q;
il void dijkstra(int u,int *dis,int &tot){
memset(vis,0,sizeof(vis));
dis[u]=0,q.push(mp(0,u));
while(q.size()){
int x=q.top().sec;
q.pop();
if(vis[x]){
continue;
}
vis[x]=1;
for(pii i:e[x]){
int v=i.fir,w=i.sec;
if(!vis[v]&&dis[v]>dis[x]+w){
dis[v]=dis[x]+w;
q.push(mp(-dis[v],v));
}
}
}
tot=0;
for(int i=1;i<=n;i++){
lsh[++tot]=dis[i];
}
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=n;i++){
dis[i]=lwrb(lsh+1,lsh+tot+1,dis[i])-lsh;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>S>>T;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
memset(dis,0x3f,sizeof(dis));
dijkstra(S,dis[0],cs);
dijkstra(T,dis[1],ct);
for(int i=1;i<=n;i++){
cnt[dis[0][i]][dis[1][i]]++;
sum[dis[0][i]][dis[1][i]]+=a[i];
}
for(int i=cs;i;i--){
for(int j=ct;j;j--){
sum[i][j]+=sum[i+1][j]+sum[i][j+1]-sum[i+1][j+1];
p[0][i][j]=min(i==cs?cs:p[0][i+1][j],j==ct?cs:p[0][i][j+1]);
p[1][i][j]=min(i==cs?ct:p[1][i+1][j],j==ct?ct:p[1][i][j+1]);
if(cnt[i][j]){
p[0][i][j]=i,p[1][i][j]=j;
}
f[0][i][j]=sum[i][j]-g[1][p[0][i][j]+1][j];
f[1][i][j]=sum[i][j]-g[0][i][p[1][i][j]+1];
g[0][i][j]=min(f[0][i][j],g[0][i][j+1]);
g[1][i][j]=min(f[1][i][j],g[1][i+1][j]);
}
}
int ans=2*f[0][1][1]-sum[1][1];
// cout<<ans<<"\n";
cout<<(ans>0?"Break a heart":ans==0?"Flowers":"Cry");
return 0;
}
}
signed main(){return asbt::main();}
浙公網(wǎng)安備 33010602011771號(hào)