526互联

AtCoder Educational DP Contest

发布时间 2023-03-25 19:27:36作者: ktq_cpp

1.A

没什么难度，直接算就可以了。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define Yes printf("Yes\n")
#define No printf("No\n")
#define YES printf("YES\n")
#define NO printf("NO\n")
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int dp[100005];
int n;
int a[100005];
signed main(){
	n=read();
	rep(i,n)a[i]=read();
	memset(dp,INF,sizeof(dp));
	dp[1]=0;
	for(int i=2;i<=n;i++){
		for(int j=i-1;j>=i-2;j--)dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
	}
	printf("%lld",dp[n]);
	return 0;
}

2.B

和上一题差不多，只不过要从 \(k\) 步之前转移来。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define Yes printf("Yes\n")
#define No printf("No\n")
#define YES printf("YES\n")
#define NO printf("NO\n")
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int dp[100005];
int n,k;
int a[100005];
signed main(){
	n=read(),k=read();
	rep(i,n)a[i]=read();
	memset(dp,INF,sizeof(dp));
	dp[1]=0;
	for(int i=2;i<=n;i++){
		for(int j=i-1;j>=max(i-k,1LL*1);j--)dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
	}
	printf("%lld",dp[n]);
	return 0;
}

3.C

令 \(dp_{i,j}\) 表示第 \(i\) 天选第 \(j\) 个活动的最大快乐值，转移即可。

话说为什么写作业有快乐值

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define Yes printf("Yes\n")
#define No printf("No\n")
#define YES printf("YES\n")
#define NO printf("NO\n")
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int dp[100005][5];
int n;
int a[100005],b[100005],c[100005];
signed main(){
	n=read();
	rep(i,n)a[i]=read(),b[i]=read(),c[i]=read();
	rep(i,n){
		dp[i][1]=max(dp[i-1][2],dp[i-1][3])+a[i];
		dp[i][2]=max(dp[i-1][1],dp[i-1][3])+b[i];
		dp[i][3]=max(dp[i-1][1],dp[i-1][2])+c[i];
	}
	printf("%lld",max(dp[n][1],max(dp[n][2],dp[n][3])));
	return 0;
}

4.D

背包板子题

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define INF 0x3f3f3f
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int n,w;
struct Item{
	int w,v;
}a[105];
int dp[100005];
signed main(){
	n=read(),w=read();
	rep(i,n){
		a[i].w=read(),a[i].v=read();
	}
	for(int i=1;i<=n;i++){
		for(int j=w;j>=a[i].w;j--){
			dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
		}
	}
	printf("%lld",dp[w]);
	return 0;
}