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;
}