状压DP杂题

news/2024/7/23 23:38:33 标签: 算法, 动态规划, 状压DP

引

好歹第一次正经学状压，好好总结一下

T1 [CQOI2018] 解锁屏幕

题目传送门

解法

状态设计：

f S , i : 连上了 S 中的所有的点并且当前处于 i 点的方案数 f_{S,i} : 连上了S中的所有的点并且当前处于i点的方案数 fS,i​:连上了S中的所有的点并且当前处于i点的方案数

状态转移：

枚举 S S S 补集里的 点 转移即可，就注意不能越过一个点到另一个点就行

Code

#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define _rep(i,j,k) for(int i=k;i>=j;i--)
using ll = long long ; 
using db = double ;
using namespace std;
const int N=20,M=(1<<20);
const ll mod=1e8+7,inv2=499122177;
int n;
ll f[M][N],g[N][N],ans;
pair<int,int> p[N];
vector<int> vec[N];
ll qpow(ll ba,ll pow) {
    ll res=1; while(pow) {
        if(pow&1) res=res*ba%mod;
        ba=ba*ba%mod,pow>>=1;
    } return res;
}
ll Add(ll x,ll y) { return ((x+y)%mod) ;}
ll Mul(ll x,ll y) { return ((x*y)%mod) ;}
ll Inv(ll x) { return qpow(x,mod-2) ;}
void init() {
    scanf("%d",&n);
    rep(i,1,n) scanf("%d%d",&p[i].first,&p[i].second);
    sort(p+1,p+1+n);
    rep(i,1,n) rep(j,i+1,n) {
        rep(k,i+1,j-1) {
            int tx=p[i].first-p[j].first,ty=p[i].second-p[j].second;
            int px=p[i].first-p[k].first,py=p[i].second-p[k].second;
            if(tx*py==ty*px) g[i][j]|=(1<<k) , g[j][i]|=(1<<k);
        }
    }
}
void work() {
    rep(i,1,n) f[1<<i][i]=1;
    rep(mask,0,(1<<(n+1))-1) rep(j,1,n) if(mask&(1<<j)) {
        for(int k=1;k<=n;k++)
            if((mask&(1<<k))==0&&k!=j&&(mask&g[j][k])==g[j][k])
                f[mask|(1<<k)][k]=Add(f[mask|(1<<k)][k],f[mask][j]);
    }
    
    rep(i,0,(1<<(n+1))-1) if(__builtin_popcount(i)>=4){
        rep(j,1,n)
            if(i&(1<<j)) ans=Add(ans,f[i][j]);
    }
    printf("%lld\n",ans);
}
int main(){
    init(),work();
}

T2 [NOIP2017 提高组] 宝藏

题目传送门

解法

状态设计：

f S , i ：点集为 S ，树高为 i 的最小代价 f_{S,i}：点集为S，树高为i的最小代价 fS,i​：点集为S，树高为i的最小代价

状态转移：

枚举 点集 作为最后一层转移即可

Code

#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define _rep(i,j,k) for(int i=k;i>=j;i--)
using ll = long long ; 
using db = double ;
using namespace std;
const int N=13,M=(1<<12)+7;
const ll mod=1e8+7,inv2=499122177,INF=1e10;
int n,m;
ll f[N][M],dis[N][M],ans=INF;
ll qpow(ll ba,ll pow) {
    ll res=1; while(pow) {
        if(pow&1) res=res*ba%mod;
        ba=ba*ba%mod,pow>>=1;
    } return res;
}
ll Add(ll x,ll y) { return ((x+y)%mod) ;}
ll Mul(ll x,ll y) { return ((x*y)%mod) ;}
ll Inv(ll x) { return qpow(x,mod-2) ;}
void init() {
    scanf("%d%d",&n,&m);
    rep(i,0,n-1) rep(mask,0,(1<<n)-1)  f[i][mask]=dis[i][mask]=INF;
    rep(i,0,n-1) f[0][1<<i]=0;
    rep(i,1,m){
        int u,v;ll w; scanf("%d%d%lld",&u,&v,&w); u--,v--;
        dis[u][1<<v]=dis[v][1<<u]=min(dis[u][1<<v],w);
    }
}
void work() {
    rep(i,0,n-1) rep(mask,0,(1<<n)-1) if(!(mask>>i&1)) {
        rep(j,0,n-1) if(mask>>j&1) 
			dis[i][mask]=min(dis[i][mask],dis[i][1<<j]);
    }
    rep(i,1,n-1) rep(mask,0,(1<<n)-1) {
        for(int S=mask;S;S=(S-1)&mask) {
            int _S=mask^S; ll len=0;
            rep(j,0,n-1) if(S>>j&1) 
                len+=dis[j][_S];
            f[i][mask]=min(f[i][mask],f[i-1][_S]+i*len);
        }
    }
    rep(i,0,n-1) ans=min(ans,f[i][(1<<n)-1]);
    printf("%lld\n",ans);
}
int main(){
    init(),work();
}

T3 [HAOI2016] 字符合并

题目传送门

解法

这题比较有意思，是个区间DP+状压DP

状态设计：

f l , r , m a s k : 区间 [ l , r ] 最后合并成 m a s k 可获得的最大分数 f_{l,r,mask}: 区间[l,r]最后合并成mask可获得的最大分数 fl,r,mask​:区间[l,r]最后合并成mask可获得的最大分数

状态转移 ：

Code

枚举断点转移即可

#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define _rep(i,j,k) for(int i=k;i>=j;i--)
using ll = long long ; 
using db = double ;
using namespace std;
const int N=307,M=(1<<12)+7,K=(1<<8)+7;
const ll mod=1e8+7,inv2=499122177,INF=1e10;
int n,k;
int a[N],c[K];
ll w[K],f[N][N][K],ans=-INF;
ll qpow(ll ba,ll pow) {
    ll res=1; while(pow) {
        if(pow&1) res=res*ba%mod;
        ba=ba*ba%mod,pow>>=1;
    } return res;
}
ll Add(ll x,ll y) { return ((x+y)%mod) ;}
ll Mul(ll x,ll y) { return ((x*y)%mod) ;}
ll Inv(ll x) { return qpow(x,mod-2) ;}
void init() {
    scanf("%d%d",&n,&k);
	rep(i,1,n) scanf("%d",&a[i]);
	rep(i,0,(1<<k)-1) scanf("%d%lld",&c[i],&w[i]);
	rep(l,0,n) rep(r,0,n) rep(mask,0,(1<<k)) f[l][r][mask]=-INF;
	rep(i,1,n) f[i][i][a[i]]=0;
}
void work() {
	rep(len,2,n) for(int l=1,r=len;r<=n;l++,r++) {
		int x=(len-1) % (k-1); if(x==0) x=k-1;
		for(int mid=r-1;mid>=l;mid-=(k-1)) rep(mask,0,(1<<x)-1) {
			f[l][r][mask<<1]=max(f[l][r][mask<<1],f[l][mid][mask]+f[mid+1][r][0]);
			f[l][r][mask<<1|1]=max(f[l][r][mask<<1|1],f[l][mid][mask]+f[mid+1][r][1]);
		}
		if(x == k-1) {
			vector<ll> g(2,-INF);
			rep(mask,0,(1<<k)-1) g[c[mask]]=max(g[c[mask]],f[l][r][mask]+w[mask]);
			f[l][r][0]=g[0],f[l][r][1]=g[1];
		}
	}
	rep(mask,0,(1<<k)-1) ans=max(ans,f[1][n][mask]);
	printf("%lld\n",ans);
}
int main(){
    init(),work();
}

T4 [NOI2015] 寿司晚宴

技巧性有点大，但不多

解法

将质因子的含有情况存进状态即可，但会 T L E TLE TLE ,所以我们考虑 根号分治 即可

Code

滚动了一下数组

#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define _rep(i,j,k) for(int i=k;i>=j;i--)
using ll = long long ; 
using db = double ;
using namespace std;
const int N=507,M=(1<<8)+7,K=(1<<8)+7;
const ll inv2=499122177,INF=1e10;
int n;
int pri[]={0,2,3,5,7,11,13,17,19,0};
ll mod,ans;
ll f[M][M],g1[M][M],g2[M][M];
struct st{
	int val,MAX,mask;
	void init() {
		MAX=-1; int tmp=val;
		rep(i,1,8) {
			// puts("!!");
			if(tmp%pri[i]) continue;
			mask|=(1<<(i-1));
			while((tmp%pri[i]==0)) tmp/=pri[i];
		}
		if(tmp!=1) MAX=tmp;
	}
	bool operator < (const st &x) const { return MAX<x.MAX; }
}a[N];
ll qpow(ll ba,ll pow) {
    ll res=1; while(pow) {
        if(pow&1) res=res*ba%mod;
        ba=ba*ba%mod,pow>>=1;
    } return res;
}
ll Add(ll x,ll y) { return ((x+y)%mod) ;}
ll Mul(ll x,ll y) { return ((x*y)%mod) ;}
ll Del(ll x,ll y) { return ((x-y)<0)?x-y+mod:x-y ;}
ll Inv(ll x) { return qpow(x,mod-2) ;}
void init() {
    scanf("%d%lld",&n,&mod); 
	rep(i,2,n) a[i-1].val=i,a[i-1].init();
	sort(a+1,a+n);
	f[0][0]=1;
}
void work() {
	rep(i,1,n-1) {
		if(a[i].MAX!=a[i-1].MAX|| a[i].MAX==-1) {
			rep(mask,0,255) rep(_mask,0,255)
				g1[mask][_mask]=g2[mask][_mask]=f[mask][_mask];
		}
		_rep(mask,0,255) _rep(_mask,0,255) if((mask&_mask)==0){
			if((a[i].mask&mask)==0) g2[mask][_mask|a[i].mask]=Add(g2[mask][_mask|a[i].mask],g2[mask][_mask]);
			if((a[i].mask&_mask)==0) g1[mask|a[i].mask][_mask]=Add(g1[mask|a[i].mask][_mask],g1[mask][_mask]);
		}
		if(i==n-1||a[i].MAX!=a[i+1].MAX|| a[i].MAX==-1) {
			rep(mask,0,255) rep(_mask,0,255) if((mask&_mask)==0) {
				f[mask][_mask]=Add(g1[mask][_mask],Del(g2[mask][_mask],f[mask][_mask]));
			}
		}
	}
	rep(mask,0,255) rep(_mask,0,255) if((mask&_mask)==0)
		ans=Add(ans,f[mask][_mask]);
	printf("%lld\n",ans);
}
int main(){
    init();
	work();
}

T5 [PKUWC2018] 随机算法

题目传送门

解法：

状态设计:

f S : 点集为 S 时的答案 f_{S}:点集为S时的答案 fS​:点集为S时的答案

状态转移：

f S = ∑ i ( f S − T i ∗ ( g S − T i + 1 = = g S ) ) ∣ S ∣ g S : S 的最大独立集的点数 T i : i 以及 i 所连的点的集合 f_{S}=\frac{\sum_{i} (f_{S-T_{i}}*(g_{S-T_{i}}+1==g_{S}) )}{|S|}\\ g_{S}:S的最大独立集的点数\\ T_{i}:i以及i所连的点的集合 fS​=∣S∣∑i​(fS−Ti​​∗(gS−Ti​​+1==gS​))​gS​:S的最大独立集的点数Ti​:i以及i所连的点的集合

Code

#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define _rep(i,j,k) for(int i=k;i>=j;i--)
#define _b_pct  __builtin_popcount 
using ll = long long ; 
using db = double ;
using namespace std;
const int N=21,M=(1<<20)+7,K=(1<<8)+7;
const ll inv2=499122177,INF=1e18,mod=998244353;
int n,m;
int G[N];
ll f[M],g[M];
ll qpow(ll ba,ll pow) {
    ll res=1; while(pow) {
        if(pow&1) res=res*ba%mod;
        ba=ba*ba%mod,pow>>=1;
    } return res;
}
ll Add(ll x,ll y) { return ((x+y)%mod) ;}
ll Mul(ll x,ll y) { return ((x*y)%mod) ;}
ll Inv(ll x) { return qpow(x,mod-2) ;}
void init() {
    scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) G[i]|=(1<<i),g[(1<<i)]=1;
	rep(i,1,m) {
		int u,v ; scanf("%d%d",&u,&v); u--,v--;
		G[u]|=(1<<v),G[v]|=(1<<u);
	}
}
void work() {
	rep(mask,1,(1<<n)-1) rep(i,0,n-1) if(mask>>i&1) {
		g[mask]=max(g[mask],g[mask&(~G[i])]+1);
	}
	f[0]=1;
	// rep(mask,1,(1<<n)-1) printf("%d: %lld\n",mask,g[mask]); puts("");
	rep(mask,1,(1<<n)-1){ 
		rep(i,0,n-1) if((mask>>i&1) && (g[mask&(~G[i])]+1==g[mask])) 
			f[mask]=Add(f[mask],f[mask&(~G[i])]) ;
		// printf("%lld %lld %lld\n",f[mask],ll(_b_pct(mask)),Inv(_b_pct(mask)));
		f[mask]=Mul(f[mask],Inv(_b_pct(mask)));
	}
	printf("%lld\n",f[(1<<n)-1]);
}
int main(){
    init();
	work();
}

T6 [ABC152F] Tree and Constraints

题目传送门

解法

容斥即可
式子写一下吧：
A n s = ∑ S ( − 1 ) ∣ S ∣ ∗ f S Ans=\sum_S (-1)^{|S|}*f_{S} Ans=S∑​(−1)∣S∣∗fS​
至于式子什么意思就自己悟吧

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <bitset>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define _rep(i,j,k) for(register int i=k;i>=j;i--)
#define _b_pct  __builtin_popcount 
using ll = long long ; 
using db = double ;
using namespace std;
const int N=107,M=3e3+7,K=(1<<8)+7,INF=1e9;
const ll inv2=499122177,LLF=1e18,mod=998244353;
int n,m,c1;
int head[N],sta[N],tp;
ll f[(1<<20)+7],p[2]={1,-1},ans,p2[M];
bitset<N> bt[22];
struct Edge{ int next,to; }e[M<<1];
void Add_Edge(int fr,int to) {
	e[c1]=(Edge) {head[fr],to};
	head[fr]=c1++;
}
ll qpow(ll ba,ll pow) {
	ll res=1; while(pow) {
		if(pow&1) res=res*ba%mod;
		ba=ba*ba%mod,pow>>=1;
	} return res;
}
ll Add(ll x,ll y) { return ((x+y)%mod) ;}
ll Mul(ll x,ll y) { return ((x*y)%mod) ;}
ll Del(ll x,ll y) { return (x-y<0?x-y+mod:x-y) ;}
ll Inv(ll x) { return qpow(x,mod-2) ;}
ll Block(ll x) {
	ll res=0;
	for(ll l=1,r;l<=x;l=r+1) {
		r=x/(x/l);
		res=Add(res,Mul((x/l),(r-l+1)));
	}
	return res;
}
void dfs(int u,int fa,int po,int id) {
	for(int i=head[u];~i;i=e[i].next) {
		int v=e[i].to; if(v==fa) continue;
		sta[++tp]=i>>1;
		if(v==po) {
			while(tp) bt[id][sta[tp]]=1,tp--;
			return ;
		} 
		dfs(v,u,po,id);
		tp--;
	}

}
void init() {
	scanf("%d",&n);
	p2[0]=1; for(int i=1;i<=n;i++) p2[i]=p2[i-1]<<1;
	memset(head,-1,sizeof head);
	for(int i=1,u,v;i<n;i++) {
		scanf("%d%d",&u,&v);
		Add_Edge(u,v),Add_Edge(v,u);
	}
	scanf("%d",&m);
	for(int i=0,u,v;i<m;i++) {
		scanf("%d%d",&u,&v);
		tp=0;
		dfs(u,0,v,i);
	}
}
void work() {
	rep(mask,0,(1<<m)-1) {
		int cnt=_b_pct(mask),num=n-1;
		bitset<N> tmp;
		rep(i,0,m-1) if(mask>>i&1) 
			tmp|=bt[i];
		num-=tmp.count();
		ans+=(p[cnt&1]*p2[num]);
	}
	printf("%lld\n",ans);
}
int main(){
    init();
	work();
}

T6 [ARC078F] Mole and Abandoned Mine

题目传送门

解法

就是求割完后满足条件的图的边权和的 最大值
状态的设计是套路的： f S , i f_{S,i} fS,i​
转移时考虑图最后的形态一定是

所以删完边后的图一定是由一条从 1 1 1 到 n n n 的链，和若干个两两之间没有连边，且与链之间仅有一条边的连通块组成 。

分成 连点 或者 连连通块 的情况转移即可
干就完了

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <bitset>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define _rep(i,j,k) for(register int i=k;i>=j;i--)
#define _b_pct  __builtin_popcount 
using ll = long long ; 
using db = double ;
using namespace std;
const int N=17,M=(1<<15)+7,INF=1e9;
const ll inv2=499122177,LLF=1e18,mod=998244353;
int n,m,k;
ll w[N][N],f[N][M],g[N][M],h[M],ans;
ll qpow(ll ba,ll pow) {
	ll res=1; while(pow) {
		if(pow&1) res=res*ba%mod;
		ba=ba*ba%mod,pow>>=1;
	} return res;
}
ll Add(ll x,ll y) { return ((x+y)%mod) ;}
ll Mul(ll x,ll y) { return ((x*y)%mod) ;}
ll Del(ll x,ll y) { return (x-y<0?x-y+mod:x-y) ;}
ll Inv(ll x) { return qpow(x,mod-2) ;}
ll Block(ll x) {
	ll res=0;
	for(ll l=1,r;l<=x;l=r+1) {
		r=x/(x/l);
		res=Add(res,Mul((x/l),(r-l+1)));
	}
	return res;
}
void init() {
	scanf("%d%d",&n,&m); k=(1<<n)-1;
	memset(f,-0x3f,sizeof f);
	rep(i,1,m) {
		int u,v; ll W; scanf("%d%d%lld",&u,&v,&W); u--,v--;
		w[u][v]=w[v][u]=W, ans+=W;
	}
}
void work() {	
	rep(i,0,n-1) rep(mask,0,(1<<n)-1) if((mask>>i&1)==0){
		rep(j,0,n-1) if(mask>>j&1) 
			g[i][mask]+=w[i][j];
	}
	rep(mask,0,(1<<n)-1) rep(i,0,n-1) rep(j,i+1,n-1) if((mask>>i&1) && (mask>>j&1)){
		h[mask]+=w[i][j];
	}
	f[0][1]=0;
	rep(mask,0,(1<<n)-1) rep(i,0,n-1) if((mask>>i&1) && (mask&1) && f[i][mask]>=0) {
		rep(j,0,n-1) if((mask>>j&1)==0 && w[i][j]>0) {
			f[j][mask|(1<<j)] = max(f[j][mask|(1<<j)],f[i][mask] + w[i][j]);
		}
		int tS=mask^k;
		for(int S=tS;S;S=(S-1)&tS) {
			f[i][mask|S]=max(f[i][mask|S],f[i][mask]+h[S]+g[i][S]);
		}
	}
	printf("%lld\n",ans-f[n-1][k]);
}	
int main(){
    init();
	work();
}

T7 Favorite Game

题目传送门

这题我就得好好讲讲了

解法

设计状态：

引用他人博客 ： 大神的博客

状态转移 ：

h , t 的含义分别为到传送门，刺杀地点的最短距离 h,t的含义分别为到传送门，刺杀地点的最短距离 h,t的含义分别为到传送门，刺杀地点的最短距离
1.从传送门到传送门：
枚举传送点转移即可
f m a s k , i + h m a s k , j → f m a s k ∣ j , i f_{mask,i}+h_{mask,j}\to f_{mask|j,i} fmask,i​+hmask,j​→fmask∣j,i​
2.从传送门到刺杀地点：
i f ( f m a s k , i + t m a s k , j ≤ t i m e j ) i + 1 → g m a s k , j if(f_{mask,i}+t_{mask,j}\le time_j) \quad i+1\to g_{mask,j} if(fmask,i​+tmask,j​≤timej​)i+1→gmask,j​
3.从刺杀地点到传送门：
t i m e i + min ⁡ ( d i s i , j , h m a s k , j ) → f m a s k ∣ j , g m a s k , i time_i+\min(dis_{i,j},h_{mask,j})\to f_{mask|j,g_{mask,i}} timei​+min(disi,j​,hmask,j​)→fmask∣j,gmask,i​​
4.从刺杀地点到刺杀地点。
i f ( t i m e j − t i m e i ≥ min ⁡ ( d i s i , j , t m a s k , j ) ) g m a s k , i + 1 → g m a s k , j if(time_j-time_i \ge \min(dis_{i,j},t_{mask,j}))\quad g_{mask,i}+1\to g_{mask,j} if(timej​−timei​≥min(disi,j​,tmask,j​))gmask,i​+1→gmask,j​

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define _rep(i,j,k) for(register int i=k;i>=j;i--)
#define _b_pct  __builtin_popcount 
using ll = long long ; 
using db = double ;
using namespace std;
const int N=107,M=(1<<14)+7,K=16,INF=2e9;
const ll inv2=499122177,LLF=1e18,mod=998244353;
int n,m,k;
int f[M][N],g[M][N];//f:时间 ; g:完成数
int h[M][N],t[M][N];//h:到传送门 ; t:到刺杀地点
struct Pos { int xa,ya; } a[N];
struct Qu { int xb,yb,t; } b[N];

bool cmp(Qu x,Qu y) { return x.t<y.t; }

ll qpow(ll ba,ll pow) {
	ll res=1; while(pow) {
		if(pow&1) res=res*ba%mod;
		ba=ba*ba%mod,pow>>=1;
	} return res;
}

ll Add(ll x,ll y) { return ((x+y)%mod) ;}

ll Mul(ll x,ll y) { return ((x*y)%mod) ;}

ll Del(ll x,ll y) { return (x-y<0?x-y+mod:x-y) ;}

ll Inv(ll x) { return qpow(x,mod-2) ;}

ll Block(ll x) {
	ll res=0;
	for(ll l=1,r;l<=x;l=r+1) {
		r=x/(x/l);
		res=Add(res,Mul((x/l),(r-l+1)));
	}
	return res;
}

int Calc(int xa,int ya,int xb,int yb) { return abs(xa-xb)+abs(ya-yb); }

void init() {
	scanf("%d%d",&n,&m); k=(1<<n)-1;
	rep(i,1,n) scanf("%d%d",&a[i].xa,&a[i].ya);
	rep(i,1,m) scanf("%d%d%d",&b[i].xb,&b[i].yb,&b[i].t);
	sort(b+1,b+1+m,cmp);
	rep(mask,0,k) {
		f[mask][0]=INF;
		rep(i,1,m) t[mask][i]=f[mask][i]=INF,g[mask][i]=-INF;
		rep(i,1,n) h[mask][i]=INF;
	}
	rep(i,0,n) f[1<<i][0]=0;
	rep(i,1,m) g[0][i]=1;
}
void work() {	
	rep(mask,0,k) rep(i,1,n) {
		rep(j,1,n) if(mask>>(j-1)&1) 
			h[mask][i]=min(h[mask][i],Calc(a[i].xa,a[i].ya,a[j].xa,a[j].ya));
	}
	rep(mask,0,k) rep(i,1,m) {
		rep(j,1,n) if(mask>>(j-1)&1) 
			t[mask][i]=min(t[mask][i],Calc(b[i].xb,b[i].yb,a[j].xa,a[j].ya));
	}
	int ans=1;
	rep(mask,0,k) {
		rep(i,0,m) if(f[mask][i]!=INF) {
			rep(j,1,n) if((mask>>(j-1)&1)==0) //f->f
				f[mask|(1<<(j-1))][i]=min(f[mask|(1<<(j-1))][i],f[mask][i]+h[mask][j]);
			rep(j,1,m) if(b[j].t>=f[mask][i]+t[mask][j]) // f->g
				g[mask][j]=max(g[mask][j],i+1),ans=max(ans,g[mask][j]);
		}
		rep(i,1,m) if(g[mask][i]!=-INF) {
			rep(j,1,n) // g->f
				f[mask|(1<<(j-1))][g[mask][i]]=min(f[mask|(1<<(j-1))][g[mask][i]], b[i].t+min(Calc(a[j].xa,a[j].ya,b[i].xb,b[i].yb),h[mask][j]) );
			rep(j,i+1,m) if(min(t[mask][j],Calc(b[j].xb,b[j].yb,b[i].xb,b[i].yb))<=b[j].t-b[i].t) // g->g
				g[mask][j]=max(g[mask][j],g[mask][i]+1),ans=max(ans,g[mask][j]);
		}
		// printf("%d %d:\n%d %d\n",mask,i,f[mask][i],g[mask][i]);
	}
	printf("%d\n",ans);
}	
int main(){
    init();
	work();
}

http://www.niftyadmin.cn/n/5049556.html

相关文章

概率深度学习建模数据不确定性

概率深度学习建模数据不确定性

https://zhuanlan.zhihu.com/p/568912284理解论文 What uncertainties do we need in Bayesian deep learning for computer vision? &#xff08;NeurIPS 2017) [1]中的数据不确定性建模&#xff0c;并给出公式推导。论文[1]指出不确定性uncertainty分为随机不确定性(aleator…
阅读更多...
03-Scala算术运算符

03-Scala算术运算符

运算符 scala运算符的使用和Java运算符的使用基本相同&#xff0c;只有个别细节上不同。 注意&#xff1a; ​ Scala中&#xff0c;没有 、-- 操作符&#xff0c;可以通过、-来实现通用的效果 ​ Scala中&#xff0c;一般情况下&#xff0c; 与 equals 是一样的&#xff…
阅读更多...
oracle11g-图形安装(centos7)

oracle11g-图形安装(centos7)

目录 一.环境准备1.关闭防火墙2.关闭SELINUX3.配置本地yum源4.安装ORACLE先决条件的软件包5.修改LINUX的内核文件6.添加下列参数到/etc/security/limits.conf7.添加下列条目到/etc/pam.d/login8.环境变量中添加下列语句9.创建文件目录和相应的用户10.配置oracle用户的环境变量1…
阅读更多...
顺序读写函数的介绍：fscanf fprintf

顺序读写函数的介绍：fscanf fprintf

目录 函数介绍&#xff1a; fprintf&#xff1a; 将结构体变量s的成员列表内容写入文件中&#xff1a; 文件效果&#xff1a;已经进行了格式化&#xff0c;3.140000是最明显的效果&#xff0c;因为float需要补齐0来补充精度 和printf的对比&#xff1a; 不同之处&#xff…
阅读更多...
无法解析插件 org.apache.maven.plugins:maven-clean-plugin:3.2.0 尝试使用 -U

无法解析插件 org.apache.maven.plugins:maven-clean-plugin:3.2.0 尝试使用 -U

无法解析插件 org.apache.maven.plugins:maven-clean-plugin:3.2.0 尝试使用 -U 报错如下&#xff1a; 解决方案&#xff1a;在文件夹里面找到报错的文件&#xff0c;删除&#xff0c;然后刷新.pom文件&#xff0c;让maven重新下载即可
阅读更多...
【.net core】使用nssm发布WEB项目

【.net core】使用nssm发布WEB项目

nssm下载地址&#xff1a;NSSM - the Non-Sucking Service Manager 配置方式 修改服务在nssm工具下输入命令:nssm edit jntyjr 其中 jntyjr为添加服务时设置的Service name
阅读更多...
云防火墙和传统防火墙区别是什么

云防火墙和传统防火墙区别是什么

云防火墙和传统防火墙的区别是什么呢&#xff1f;在当前的网络环境中&#xff0c;网络安全问题日益复杂且频发&#xff0c;企业和个人都需要在保护网络的同时确保数据的安全性。为此&#xff0c;防火墙作为一种重要的网络安全设备&#xff0c;发挥着关键的作用。然而&#xff0…
阅读更多...
PHP脚本导出MySQL数据库

PHP脚本导出MySQL数据库

背景&#xff1a;有时候需要同步数据库的表结构和部分数据&#xff0c;同步全表数据非常大&#xff0c;也不适合。还有一个种办法是使用数据库的dump命令执行备份&#xff0c;无法进入服务器&#xff1f;没有权限怎么办&#xff1f; 这里只要能访问服务器中的 information_sch…
阅读更多...
最新文章

Copyright @ 2022~2023