A. 小奇挖矿2

显然的O(m)dp：$f[i]=max(f[i-4],f[i-7])+a[i]$，当然你要保证i，i-4，i-7都能到达

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define re register

using namespace std;

const int MAXN=1e7+5;

int n,m,a[MAXN],b[MAXN],ans=0,f[MAXN];

signed main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%d%d",&a[i],&b[i]);

		f[b[i]]+=a[i];

	}

	for(int i=0;i<=3;i++) f[i]=-1;

	for(int i=5;i<=6;i++) f[i]=-1;

	ans=max(f[4],f[7]);

	for(int i=8;i<=m;i++){

		if(f[i-4]==-1&&f[i-7]==-1){

			f[i]=-1;

			continue;

		}

		f[i]+=max(f[i-4],f[i-7]);

		ans=max(ans,f[i]);

	}

	printf("%d\n",ans);

	return 0;

}

然后我们优化，我们发现如果两点之间的距离超过18就一定能到达，所以我们把距离压缩一下

具体为什么你需要做一下NOIP2017小凯的疑惑

然后就AC了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define re register

using namespace std;

const int MAXN=2e6+5;

int n,m,a[MAXN],b[MAXN],ans=0,f[MAXN];

struct node{

	int a,b;

	friend bool operator < (node x,node y){

		return x.b==y.b?x.a<y.a:x.b<y.b;

	}

}mine[MAXN];

signed main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d%d",&mine[i].a,&mine[i].b);

	sort(mine+1,mine+n+1);

	for(int i=1;i<=n;i++){

		if(mine[i].b-mine[i-1].b>17)

			a[i]=mine[i].a,b[i]=b[i-1]+18;

		else a[i]=mine[i].a,b[i]=b[i-1]+(mine[i].b-mine[i-1].b);

	}

	for(int i=1;i<=n;i++) f[b[i]]+=a[i];

	for(int i=0;i<=3;i++) f[i]=-1;

	for(int i=5;i<=6;i++) f[i]=-1;

	m=b[n];

	ans=max(f[4],f[7]);

	for(int i=8;i<=m;i++){

		if(f[i-4]==-1&&f[i-7]==-1){

			f[i]=-1;

			continue;

		}

		f[i]+=max(f[i-4],f[i-7]);

		ans=max(ans,f[i]);

	}

	printf("%d\n",ans);

	return 0;

}

还有一种解决方法：

将所有矿物排序，f[i]为到第i个矿体能获得的最大原矿数，那么f[i]=max{f[j]}+x[i]，其中，i-j满足能拆分成4和7。

这样dp需要n²的复杂度，但是我们发现，相距超过17的一定可达，那么不超过17的范围内暴力，超过17的取个最大值即可，复杂度O(n)

from skyh：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

const int N=1e5+10;

map<int,int> mp;

int n,m,ans,cnt;

int dp[N],mx[N];

bool ok[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0};//0 4 7 8 11 12 14 15 16  >17

inline int read(register int x=0,register char ch=getchar(),bool ff=0){

	while(!isdigit(ch)) ff=ch=='-',ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return ff?-x:x;

}

struct node{

	int val,pos;

	friend bool operator < (const node &a,const node &b){

		return a.pos<b.pos;

	}

}k[N];

int main(){

	//freopen("x.in","r",stdin);

	//freopen("me.out","w",stdout);

	n=read(); m=read();

	for(int i=1,v,p,o;i<=n;++i){

		v=read(),p=read();

		if(!mp[p]) mp[p]=++cnt;

		o=mp[p]; k[o].pos=p; k[o].val+=v;

	}

	sort(k+1,k+cnt+1);

	memset(dp,-0x3f,sizeof(dp));

	dp[0]=0;

	for(int i=1;i<=cnt;++i){

		for(int j=i-1;~j;--j){

			if(k[i].pos-k[j].pos<=17&&ok[k[i].pos-k[j].pos]) dp[i]=max(dp[i],dp[j]+k[i].val);

			if(k[i].pos-k[j].pos>17){

				dp[i]=max(dp[i],mx[j]+k[i].val);

				break;

			}

		}

		ans=max(ans,dp[i]);

		mx[i]=max(mx[i-1],dp[i]);

	}

	printf("%d\n",ans);

	return 0;

}

B：小奇的矩阵(matrix)

平均数这玩意显然可拆：令$sum=\sum A_i$，$sqr=\sum A_{i}^{2}$

$Aavg=\frac{sum}{n+m-1}$

所以：原式=$(n+m-1)*sqr-sum^2$，推一下就能推出来

然后。。。我竟然去想了搜索！

正解dp：设$f[s][i][j]$表示到了点(i,j)，总和为s时的最小sqr值

所以f[s][i][j]=min(f[s-a[i][j]][i][j-1]+a[i][j]*a[i][j],f[s-a[i][j]][i-1][j]+a[i][j]*a[i][j]);

然后就做出来了

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x3f3f3f3f

#define re register

using namespace std;

int t,n,m,a[35][35],ans,f[1805][35][35];

signed main(){

	scanf("%d",&t);

	while(t--){

		scanf("%d%d",&n,&m);

		for(re int i=1;i<=n;i++)

			for(re int j=1;j<=m;j++)

				scanf("%d",&a[i][j]);

		ans=inf;

		memset(f,0x3f,sizeof(f));

		f[a[1][1]][1][1]=a[1][1]*a[1][1];

		for(re int i=1;i<=n;i++){

			for(re int j=1;j<=m;j++)

				for(re int k=1;k<=1800;k++){

					if(k<a[i][j]) continue;

					f[k][i][j]=min(f[k][i][j],f[k-a[i][j]][i-1][j]+a[i][j]*a[i][j]);

					f[k][i][j]=min(f[k][i][j],f[k-a[i][j]][i][j-1]+a[i][j]*a[i][j]);

				}

		}

		for(re int k=1;k<=1800;k++){

			if(f[k][n][m]>=inf) continue;

			ans=min(ans,(n+m-1)*f[k][n][m]-k*k);

		}

		printf("%d\n",ans);

	}

	return 0;

}

C：小奇的仓库(warehouse)

美妙的换根dp

设f[i][j]表示i到其他点，后4位状态为j的路径数

f[x][0]=1

f[x][(j+w)%16]+=f[y][j]

f[y][(j+w)%16]+=(f[x][j]-f[y][((j-w)%16+16)%16])

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cmath>

#define MAXN 100005

#define int long long

using namespace std;

int n,m,ans=0;

int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0,w[MAXN<<1];

void add(int u,int v,int val){

	cnt++,to[cnt]=v,w[cnt]=val,nxt[cnt]=pre[u],pre[u]=cnt;

}

int g[MAXN],f[MAXN][17],t[MAXN][17];

void DFS(int x,int fa){

	f[x][0]=1;

	for(int i=pre[x];i;i=nxt[i]){

		int y=to[i];

		if(y==fa) continue;

		DFS(y,x);

		g[x]+=g[y];

		for(int j=0;j<16;j++){

            f[x][(j+w[i])&15]+=f[y][j];

			g[x]+=f[y][j]*w[i];

		}

	}

}

void dfs(int x,int fa){

	for(int i=pre[x];i;i=nxt[i]){

		int y=to[i];

		if(y==fa) continue;

		int size=0;

		for(int j=0;j<16;j++){

			t[y][(j+w[i])&15]+=f[x][j]-f[y][((j-w[i])&15+16)&15];

			size+=f[y][j];

		}

		g[y]=g[x]+(n-size*2)*w[i];

		for(int j=0;j<16;j++) f[y][j]+=t[y][j];

		dfs(y,x);

	}

}

signed main(){

	scanf("%lld%lld",&n,&m);

	for(int i=1,u,v,val;i<n;i++){

		scanf("%lld%lld%lld",&u,&v,&val);

		add(u,v,val),add(v,u,val);

	}

	DFS(1,0);

	dfs(1,0);

	for(int i=1;i<=n;i++){

		for(int j=0;j<16;j++){

            int k=j^m;

            g[i]+=(k-j)*f[i][j];

        }

        printf("%lld\n",g[i]-m);

	}

	return 0;

}

巴特西

HZOI20190820模拟27题解

A. 小奇挖矿2

最新文章

热门文章