上班

C++(g++ 7.5.0) 解法, 执行用时: 580ms, 内存消耗: 469980K, 提交时间: 2023-02-03 22:50:30

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int i,j,k,n,m,t,it,fk[10050],sz[10050];
ll f[10050][10050],g[10050],h[10050],w[10050],res,res2;
map<tuple<int,int,int,int> ,bool> fuck;
vector<pair<int,int> >d={{1,0},{-1,0},{0,1},{0,-1}};
vector<int> v[10050];

void dfs(int x,int fa){
	
	if(x==it){
		fk[x]=1;
	}
	for(auto i:v[x]){
		if(i==fa)continue;
		dfs(i,x);
		fk[x]|=fk[i];
	}
	//printf("NMSL%d %d %d\n",x,fa,fk[x]);
	
}

void dfs2(int x,int fa){
	int i,j,k;
	
	for(auto i:v[x]){
		if(i==fa)continue;
		if(fk[i])continue;
		dfs2(i,x);
		memcpy(h,f[x],sizeof(h));
		for(j=0;j<=sz[x];j++){
			for(k=0;k<=sz[i];k++){
				h[j+k]=max(h[j+k],f[x][j]+f[i][k]);
			}
		}
		sz[x]+=sz[i];
		memcpy(f[x],h,sizeof(h));
	}
	
	if(!fk[x]){
		sz[x]++;
		for(i=10000;i>=1;i--){
			f[x][i]=f[x][i-1]+w[x];
		}
		f[x][0]=0;
	}
	
	//cout<<"NMSL "<<x<<endl;for(i=0;i<=sz[x];i++){cout<<f[x][i]<<' ';}cout<<endl;
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>t;
	n++;m++;t++;
	vector<vector<int> >a(n+5,vector<int>(m+5)),id;
	id=a;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin>>a[i][j];
			id[i][j]=++it;
			w[it]=a[i][j];
		}
	}
    
	for(i=1;i<=(n-1)*(m-1);i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		x1++;y1++;x2++;y2++;
		fuck[{x1,y1,x2,y2}]=1;
		fuck[{x2,y2,x1,y1}]=1;
	}

	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			for(auto [dx,dy]:d){
				dx+=i;dy+=j;
				if(dx<=0||dx>n||dy<=0||dy>m)continue;
				if(fuck.count({i,j,dx,dy}))continue;
				//printf("nmsl%d %d\n",id[i][j],id[dx][dy]);
				v[id[i][j]].push_back(id[dx][dy]);
			}
		}
	}
    //assert(it<=20000);
	dfs(1,0);
	for(i=1;i<=it;i++){
		if(!fk[i])continue;
		res+=w[i];w[i]=0;
		dfs2(i,0);
		t--;
		memcpy(h,g,sizeof(g));
		for(j=0;j<=sz[i];j++){
			for(k=0;k+j<=it;k++){
				h[k+j]=max(h[k+j],f[i][j]+g[k]);
			}
		}
		memcpy(g,h,sizeof(g));
	}
    assert(t>=0);
	for(i=0;i<=it;i++){
		if(i*2<=t){
			res2=max(res2,g[i]);
		}
	}
	cout<<res+res2;
}

C++(clang++ 11.0.1) 解法, 执行用时: 609ms, 内存消耗: 785416K, 提交时间: 2023-02-03 20:33:32

#include<bits/stdc++.h>
#define re //register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
int t,n,m,a[10002],ans,A,B,R[1000002],stk[1000002],tp,tot,pos[5002][5002],dep[10005],in[10005],siz[10005];
long long h[10005][10005],tmp[10005];
char f[5002][5002],g[5002][5002];
vector<int>G[10005];
inline void add(re int x,re int y){
	G[x].push_back(y),G[y].push_back(x); 
}
inline void dfs(re int x,re int y){
	dep[x]=dep[y]+1;in[x]=pos[n][m]==x,siz[x]=1;
	for(re int i=0;i<=10000;++i)h[x][i]=a[x];
	for(auto z:G[x])
		if(z^y){
			dfs(z,x),in[x]|=in[z];
			memset(tmp,-0x3f,sizeof(tmp));
			for(re int i=0;i<=siz[x];++i)
				for(re int j=0;j<=siz[z];++j)
					tmp[i+j+1]=max(tmp[i+j+1],h[x][i]+h[z][j]);
			if(!in[z]){
				for(re int i=0;i<=siz[x];++i)tmp[i]=max(tmp[i],h[x][i]);
			}siz[x]+=siz[z];
			for(re int i=0;i<=siz[x];++i)h[x][i]=tmp[i];
		}
}
signed main(){
	n=read(),m=read(),A=read();
	for(re int i=0;i<=n;++i)
		for(re int j=0;j<=m;++j)
			pos[i][j]=++tot;
	for(re int i=0;i<=n;++i)
		for(re int j=0;j<=m;++j)
			a[pos[i][j]]=read();
	for(re int i=1;i<=n*m;++i){
		re int a1=read(),b1=read(),a2=read(),b2=read();
		if(a1>a2)swap(a1,a2);if(b1>b2)swap(b1,b2);
		if(b2>b1)f[a1][b1]=1;
		else g[a1][b1]=1; 
	}
	for(re int i=0;i<=n;++i)
		for(re int j=0;j<=m;++j){
			if(!f[i][j]&&j!=m)add(pos[i][j],pos[i][j+1]);
			if(!g[i][j]&&i!=n)add(pos[i][j],pos[i+1][j]); 
		}
	dfs(1,1),A+=dep[pos[n][m]]-1;
	A>>=1;
	long long ans=0;
	for(re int i=0;i<=min(A,tot);++i)ans=max(ans,h[pos[0][0]][i]);
	printf("%lld",ans);
}

详情