NOIP2017提高組DAY2T2 - 寶藏

傳送門

Chating

說實話，NOIP的暴力分都挺好拿的

比如這道題，前40%的資料，随便亂搞都可以拿到手（畢竟 n n n如此之小）

然後思考一下正解，感覺可以狀壓,但是并不知道怎麼搞。。

後來手賤翻了題解，暴擊++++

很很（hao）簡（li）單（jie）的狀壓啊

打算練習一下狀壓（但是ldw老師說這個dp嘛，練了提升也不大。。我有點方）

Analysis

可以枚舉起點i，設立數組dp[S]表示以i為起點且到達狀态S所需要的最小費用，是以答案就是 M i n ( d p [ 2 n − 1 ] ) Min(dp[2^n−1]) Min(dp[2n−1])

然後從起點開始搜尋，每一次枚舉已經挖掘的所有點（設目前點為j，目前狀态為S），再枚舉這一次要打通的點k。記錄dep[j]表示從j到起點經過的點的數量，也就是題目中的K。則

d p [ S ∣ k ] = M i n ( d p [ S ] + d e p [ j ] ∗ c o s t ( j → k ) ) dp[S|k]=Min(dp[S]+dep[j]∗cost(j→k)) dp[S∣k]=Min(dp[S]+dep[j]∗cost(j→k))

這樣的複雜度并不是N!，因為dp數組是有條件更新的（有點類似記搜）

（但仍然不知道複雜度怎麼算，應該是 O （ 能 過 ） O（能過） O（能過）吧）

Code（100pts）

#include<bits/stdc++.h>
#define in read()
#define N 30
#define M 2009
#define ll long long
using namespace std;
inline int read(){
    int data=0;int w=1; char ch=0;
    ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return data*w;
}
int n,m;
int f[20][20],inf;
ll dp[5000],dep[20],ans=(1ll<<62)-1;
inline void dfs(int sta){
	for(int i=1;i<=n;++i){//枚舉在狀态S中的點 
		if(!(sta&(1<<i-1))) continue;
		for(int j=1;j<=n;++j){//枚舉下一個要更新的點 
			if(sta&(1<<j-1)) continue;
			if(f[i][j]==inf) continue;
			if(dp[sta]+dep[i]*1ll*f[i][j]<dp[sta|(1<<j-1)]){
				dp[sta|(1<<j-1)]=dp[sta]+dep[i]*1ll*f[i][j];
				dep[j]=dep[i]+1;
				dfs(sta|(1<<j-1));
			}
		}
	}
}
int main(){
	n=in;m=in;
	memset(f,127/3,sizeof(f));
	inf=f[0][0];
	int i,j,u,v,w;
	for(i=1;i<=m;++i){
		u=in;v=in;w=in;
		if(w<f[u][v])	f[u][v]=f[v][u]=w;
	}
	for(i=1;i<=n;++i){
		memset(dep,0,sizeof(dep));
		memset(dp,127/3,sizeof(dp));
		dep[i]=1;
		dp[(1<<i-1)]=0;
		dfs(1<<i-1);
		ans=min(ans,dp[(1<<n)-1]);
	}
	cout<<ans;
	return 0;
}
           

Code（40pts）

#include<bits/stdc++.h>
#define in read()
#define N 30
#define M 2009
#define ll long long
using namespace std;
inline int read(){
    int data=0;int w=1; char ch=0;
    ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return data*w;
}
int n,m;
int nxt[M],to[M],head[N],w[M],ecnt=0;
int f[20][20],inf;
inline void add(int x,int y,int z){
	nxt[++ecnt]=head[x];head[x]=ecnt;to[ecnt]=y;w[ecnt]=z;
}
int main(){
	n=in;m=in;
	memset(f,127/3,sizeof(f));//果然啊。。不能開太大，相加容易爆int 
	inf=f[0][0];
	int i,j,k,u,v,w,flag=0,ww;
	for(i=1;i<=m;++i){
		u=in;v=in;w=in;
		add(u,v,w);add(v,u,w);
		f[u][v]=f[v][u]=1;
		if(i!=1&&w!=ww) flag=1;
		ww=w;
	}
	for(i=1;i<=n;++i) f[i][i]=0;
	if(!flag){
		for(k=1;k<=n;++k)
			for(i=1;i<=n;++i)
				for(j=1;j<=n;++j)
					if(f[i][k]+f[k][j]<f[i][j]) f[i][j]=f[i][k]+f[k][j];
		ll ans=(1ll<<62)-1;
		for(i=1;i<=n;++i){//枚舉每一個點，作為贊助商幫忙開發的寶藏屋 
			ll tmp=0;
			for(j=1;j<=n;++j){
				if(i==j) continue;
				if(f[i][j]==inf) break;
				tmp+=f[i][j]*1ll*w;
			}
			if(j<=n) continue;
			ans=min(tmp,ans);
		}		
		cout<<ans;
	}
	return 0;
}
           

後記

NOIP

Day1，2

T1必須要拿下

T2争取拿下

T3暴力拿完